Submission #412316

#	Time	Username	Problem	Language	Result	Execution time	Memory
412316		ngpin04	Port Facility (JOI17_port_facility)	C++14	100 / 100	1281 ms	144036 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;

vector <pair <int, int>> s[3];
vector <int> adj[N];

pair <int, int> a[N];

int id[2 * N];
int c[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) {
	return (par[u] < 0) ? u : (par[u] = getpar(par[u]));
}

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

void dfs(int u) {
	for (int v : adj[u]) {
		if (!c[v]) {
			c[v] = 3 - c[u];
			dfs(v);
		} else if (c[u] == c[v]) {
			cout << 0;
			exit(0);
		}
	}
}

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 pos = u;
			while (pos <= cur) {
				int lo = pos;
				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;
				}
				pos = getnxt(hi);
				if (pos <= cur) {
					adj[u].push_back(pos);
					adj[pos].push_back(u);
					assert(join(u, pos));
				}
			}
			nxt[u] = u + 1;
		}
	}

	for (int i = 1; i <= n; i++)
		if (!c[i]) 
			c[i] = 1, dfs(i);

	for (int i = 1; i <= 2; i++)
		s[i].push_back(mp(0, 2 * n + 1));

	for (int i = 1; i <= 2 * n; i++) {
		int u = abs(id[i]);
		if (id[i] < 0) 
			s[c[u]].pop_back();
		else {
			if (a[u].se > s[c[u]].back().se) 
				return cout << 0, 0;
			s[c[u]].push_back(a[u]);
		}
	}

	int ans = 1;

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

	cout << ans;
	return 0;	
}

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