Submission #412037

#	Time	Username	Problem	Language	Result	Execution time	Memory
412037		ngpin04	Port Facility (JOI17_port_facility)	C++14	0 / 100	3 ms	460 KiB

port_facility

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
using namespace std;
const int N = 1e6 + 5; 
const int mod = 1e9 + 7;

pair <int, int> a[N];

int id[2 * N];
int c[N];
int add[N];
int nxt[N];
int par[N];
int n;

int getnxt(int u) {
	return (nxt[u] == u || nxt[u] == 0) ? u : (nxt[u] = getnxt(nxt[u]));
}

int getpar(int u) {
	if (par[u] < 0) 
		return u;
	int p = getpar(par[u]);
	c[u] = c[par[u]] ^ 1;
	return p;
}

bool join(int u, int v) {
	if (getpar(u) == getpar(v)) {
		if (c[u] == c[v]) {
			cout << 0;
			exit(0);
		}
		return false;
	}
	u = getpar(u);
	v = getpar(v);
	if (par[u] > par[v])
		swap(u, v);
	par[u] += par[v];
	par[v] = u;
	return true;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) 
		cin >> a[i].fi >> a[i].se;
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		id[a[i].fi] = i;
		id[a[i].se] = -i;
	}

	for (int i = 1, cur = 0; i <= 2 * n; i++) {
		int u = abs(id[i]);
		if (id[i] > 0) {
			nxt[u] = u;
			par[u] = -1;
			cur = u;
		} else {
			int lo = u;
			int hi = n + 1;
			while (hi - lo > 1) {
				int mid = (lo + hi) >> 1;
				int nxtmid = getnxt(mid);
				if (nxtmid <= cur && getpar(nxtmid) == getpar(u))
					lo = mid;
				else 
					hi = mid;
			}
			if (lo > u) 
				join(u, lo);
			for (int j = getnxt(hi); j <= cur; j = getnxt(j + 1)) {
				assert(join(u, j));
			}

			nxt[u] = u + 1;
		}
	}

	int ans = 1;

	for (int i = 1; i <= n; i++)
		if (par[i] < 0)
			ans = ans * 2 % mod;

	cout << ans;
	return 0;	
}

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