Submission #97321

#	Time	Username	Problem	Language	Result	Execution time	Memory
97321		shoemakerjo	Port Facility (JOI17_port_facility)	C++14	100 / 100	2555 ms	85608 KiB

port_facility

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define pii pair<int, int>

const int maxn = 1000010;
int mod = 1000000007;
int N;

ll ans, inv2;
vector<pii> vals;

int par[maxn*2];

int findset(int u) {
	if (par[u] == u) return u;

	return par[u] = findset(par[u]);
}

void unionset(int a, int b) {
	a = findset(a);
	b = findset(b);
	if (a != b) {
		par[a] = b;
	}
}

map<int, int> mp;

bool used[maxn*2];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N;
	int a, b;
	for (int i = 0; i < N; i++) {
		cin >> a >> b;
		vals.push_back(pii(a, b));
	}	
	sort(vals.begin(), vals.end());

	for (int i = 0; i < 2*N; i++) {
		par[i] = i;
	}

	for (int i = 0; i < N; i++) {
		a = vals[i].first;
		b = vals[i].second;
		auto fi = mp.lower_bound(a), se = mp.lower_bound(b);

		while (fi != se) {
			unionset(i, (fi -> second) + N);
			unionset(i + N, fi -> second);

			if (findset((--se) -> second) == findset(fi -> second)) {
				break;
			}
			++fi;
			++se;
		}

		mp[b] = i;
	}

	ans = 1;
	for (int i = 0; i < N; i++) {
		if (findset(i) == findset(i+N)) ans = 0;
		used[findset(i)] = true;
		used[findset(i+N)] = true;
	}
	for (int i = 0; i < N; i++) {
		if (used[i]) ans = (ans*2LL)%mod;
	}
	cout << ans << endl;

}

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