Submission #30974

#	Time	Username	Problem	Language	Result	Execution time	Memory
30974		szawinis	Port Facility (JOI17_port_facility)	C++14	100 / 100	2053 ms	65088 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
const long long MOD = (1e9)+7;

inline bool chk_comp(pair<int,int> x, pair<int,int> y) {
	return x.first < y.first && x.second < y.second;
}

int n;
long long ans = 1;
vector<pair<int,int> > a;
vector<int> dsu;
set<pair<int,int> > st;

int root(int v) { return (dsu[v] < 0 ? v : dsu[v] = root(dsu[v])); }
void merge(int u, int v) {
	if((u = root(u)) == (v = root(v))) return;
	if(dsu[u] > dsu[v]) swap(u, v);
	dsu[u] += dsu[v];
	dsu[v] = u;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	dsu.assign(n << 1, -1);
	for(int i = 0, l, r; i < n; i++) {
		cin >> l >> r;
		a.emplace_back(l, r);
	}
	sort(a.begin(), a.end());
	for(int i = 0, l, r; i < n; i++) {
		tie(l, r) = a[i];
		while(!st.empty() && st.begin()->first < l) st.erase(st.begin());
		auto lim = st.upper_bound(make_pair(r, INT_MAX));
		if(st.empty() || lim == st.begin()) {
			st.emplace(r, i);
			continue;
		}
		auto last = lim; --last;
		for(auto it = st.begin(); it != lim; it++) {
			merge(i, it->second + n); // a b
			merge(i + n, it->second); // b a
			if(root(it->second) == root(last->second)) break;
		}
		st.emplace(r, i);
	}
	int cc = 0;
	for(int i = 0; i < n; i++) {
		cc += dsu[i] < 0;
		if(root(i) == root(i + n)) cout << 0, exit(0);
	}
	long long base = 2;
	while(cc) {
		if(cc & 1) ans = ans * base % MOD; 
		base = base * base % MOD;
		cc >>= 1;
	}
	cout << ans;
}

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