Submission #77736

#	Time	Username	Problem	Language	Result	Execution time	Memory
77736		szawinis	Port Facility (JOI17_port_facility)	C++17	100 / 100	2446 ms	560692 KiB

port_facility

#include <bits/stdc++.h>
#define long long long
using namespace std;
const long MOD = 1e9+7;
const int N = 1 << 21;

struct seg {
	int l, r, i;
	seg() { l = r = i = MOD; }
	seg(int l, int r, int i): l(l), r(r), i(i) {}
	seg(int r): r(r) { l = i = MOD; }
	bool operator<(const seg& rhs) const { return r < rhs.r; }
};

int n;
vector<seg> a;
set<seg> st;

int dsu[N];
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;
	dsu[u] += dsu[v];
	dsu[v] = u;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	for(int i = 0, x, y; i < n; i++) {
		cin >> x >> y;
		a.emplace_back(x, y, i);
	}
	fill(dsu, dsu+N, -1);
	sort(a.begin(), a.end(), [] (seg x, seg y) { return x.l < y.l; });
	for(seg s: a) {
		while(!st.empty() && st.begin()->r < s.l) st.erase(st.begin());

		auto ed = st.upper_bound(seg(s.r));
		if(st.empty() || ed == st.begin()) {
			st.insert(s);
			continue;
		}

		for(auto it = st.begin(); it != ed; it++) {
			int u = s.i, v = it->i;
			merge(u, v + n);
			merge(u + n, v);
			if(root(v) == root(prev(ed)->i)) break;
		}	

		st.insert(s);
	}
	for(int i = 0; i < n; i++) if(root(i) == root(i + n)) cout << 0, exit(0);
	long ans = 1;
	for(int i = 0; i < n; i++) if(root(i) == i) ans = ans * 2 % MOD;
	cout << ans;
}

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