Submission #77663

#	Time	Username	Problem	Language	Result	Execution time	Memory
77663		szawinis	Port Facility (JOI17_port_facility)	C++17	0 / 100	5 ms	4472 KiB

port_facility

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

struct seg {
	int l, r, i;
	seg() { l = r = i = MOD; }
	seg(int l, int r, int i): l(l), r(r), i(i) {}
	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;
		--x, --y;
		a.emplace_back(x, y, i);
	}
	fill(dsu, dsu+N, -1);
	sort(a.begin(), a.end());
	priority_queue<pair<seg, int> > pq;
	for(seg s: a) {
		pair<seg, int> add = {s, -1};
		while(!pq.empty() && pq.top().first.r > s.l) {
			if(a[pq.top().first.i].l < s.l && pq.top().second > s.l) cout << 0, exit(0);
			if(pq.top().first.l < s.l) {
				add.first.l = min(pq.top().first.l, add.first.l);
				add.second = max(pq.top().first.r, add.second);
				merge(pq.top().first.i, s.i);
			}
			pq.pop();
		}
		pq.push(add);
	}
	long ans = 1;
	for(int i = 0; i < n; i++) if(root(i) == i) ans = ans * 2 % MOD;
	cout << ans;
}

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