Submission #712423

#	Time	Username	Problem	Language	Result	Execution time	Memory
712423		Radin_Zahedi2	Port Facility (JOI17_port_facility)	C++17	100 / 100	1484 ms	114572 KiB

port_facility

#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
using ll = long long;
using ld = long double;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'
const int mod = 1e9 + 7;
const int inf = 2e9 + 5;
const ll linf = 9e18 + 5;


int n;
const int N = 1e6 + 5;
const int L = (1 << 21);
int seg[L << 1][2];

int arr[2 * N];

int a[N];
int b[N];

bool mark[N];
bool color[N];

void cre() {
	for (int ind = L; ind < (L << 1); ind++) {
		seg[ind][0] = -1;
		seg[ind][1] = 2 * n;
	}

	for (int i = 1; i <= n; i++) {
		seg[a[i] + L][0] = b[i];
		seg[b[i] + L][1] = a[i];
	}


	for (int ind = L - 1; ind >= 1; ind--) {
		seg[ind][0] = max(seg[ind << 1][0], seg[ind << 1 | 1][0]);
		seg[ind][1] = min(seg[ind << 1][1], seg[ind << 1 | 1][1]);
	}
}

void rem(int x) {
	int ind;

	ind = a[x] + L;
	seg[ind][0] = -1;
	ind >>= 1;
	while (ind) {
		seg[ind][0] = max(seg[ind << 1][0], seg[ind << 1 | 1][0]);

		ind >>= 1;
	}

	ind = b[x] + L;
	seg[ind][1] = 2 * n;
	ind >>= 1;
	while (ind) {
		seg[ind][1] = min(seg[ind << 1][1], seg[ind << 1 | 1][1]);

		ind >>= 1;
	}
}

pair<int, int> get(int b, int e) {
	e++;

	b += L;
	e += L;

	pair<int, int> ans = mp(-1, 2 * n);
	while (b != e) {
		if (b & 1) {
			ans.fi = max(ans.fi, seg[b][0]);
			ans.se = min(ans.se, seg[b][1]);

			b++;
		}
		if (e & 1) {
			e--;

			ans.fi = max(ans.fi, seg[e][0]);
			ans.se = min(ans.se, seg[e][1]);
		}

		b >>= 1;
		e >>= 1;
	}

	return ans;
}

void init() {
}

void input() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];

		a[i]--;
		b[i]--;

		arr[a[i]] = i;
		arr[b[i]] = i;
	}
}

void dfs(int u) {
	if (!u) {
		throw;
	}
	rem(u);
	mark[u] = true;

	while (true) {
		int val = get(a[u], b[u]).fi;
		if (val == -1 || val < b[u]) {
			break;
		}

		int v = arr[val];
		color[v] = !color[u];
		dfs(v);
	}

	while (true) {
		int val = get(a[u], b[u]).se;
		if (val == 2 * n || val > a[u]) {
			break;
		}

		int v = arr[val];
		color[v] = !color[u];
		dfs(v);
	}
}

void solve() {
	cre();

	int ans = 1;
	for (int i = 1; i <= n; i++) {
		if (!mark[i]) {
			dfs(i);
			ans = (2 * ans) % mod;
		}
	}


	vector<int> v;

	for (int i = 0; i < 2 * n; i++) {
		int ind = arr[i];
		if (color[ind]) {
			continue;
		}

		if (b[ind] == i) {
			if (v.back() != ind) {
				cout << 0;
				return;
			}

			v.pop_back();
		}
		else {
			v.pb(ind);
		}
	}

	for (int i = 0; i < 2 * n; i++) {
		int ind = arr[i];
		if (!color[ind]) {
			continue;
		}

		if (b[ind] == i) {
			if (v.back() != ind) {
				cout << 0;
				return;
			}

			v.pop_back();
		}
		else {
			v.pb(ind);
		}
	}

	cout << ans;
}

void output() {
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int number_of_testcases = 1;
	//cin >> number_of_testcases;
	while (number_of_testcases--) {
		init();

		input();

		solve();

		output();
	}

	return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 22 / 22