Submission #77716

#	Time	Username	Problem	Language	Result	Execution time	Memory
77716		szawinis	Port Facility (JOI17_port_facility)	C++17	0 / 100	10 ms	9076 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, prer;
	seg() { l = r = i = MOD; prer = -1; }
	seg(int l, int r, int i): l(l), r(r), i(i) { prer = -1;}
	bool operator<(const seg& rhs) const { return r < rhs.r; }
};

int n;
vector<seg> a;

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());
	priority_queue<seg> pq;
	for(seg s: a) {
		vector<seg> to_add;
		seg add = s;
		while(!pq.empty() && pq.top().r > s.l) {
			seg tmp = pq.top();
			pq.pop();
			if(tmp.l > s.l) {
				to_add.push_back(tmp);
				continue;
			}
			add.l = min(tmp.l, add.l);
			merge(tmp.i, s.i + n); 
			merge(tmp.i + n, s.i);
		}
		pq.push(add);
		for(seg todo: to_add) pq.push(todo);
	}
	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 || root(i + n) == i + n) ans = ans * 2 % MOD;
	cout << ans;
}

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