Submission #77721

#	Time	Username	Problem	Language	Result	Execution time	Memory
77721		szawinis	Port Facility (JOI17_port_facility)	C++17	22 / 100	6102 ms	20984 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;

struct dsu {
	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;
	}
} chk_dsu, ans_dsu;

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(chk_dsu.dsu, chk_dsu.dsu+N, -1);
	fill(ans_dsu.dsu, ans_dsu.dsu+N, -1);
	sort(a.begin(), a.end());
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(a[i].l < a[j].l && a[j].l < a[i].r && a[i].r < a[j].r) {
				chk_dsu.merge(j+n, i);
				chk_dsu.merge(i+n, j);
				ans_dsu.merge(i, j);
				// cout << i << ' ' << j << a[i].l << ' ' << a[i].r << ' ' << a[j].l << ' ' << a[j].r << endl;
			}
		}
	}
	// 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);
	// 		cout << "link " << tmp.i << ' ' << s.i << endl;
	// 		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(chk_dsu.root(i) == chk_dsu.root(i + n)) cout << 0, exit(0);
	long ans = 1;
	for(int i = 0; i < n; i++) if(ans_dsu.root(i) == i) ans = ans * 2 % MOD;
	cout << ans;
}

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