Submission #77547

#	Time	Username	Problem	Language	Result	Execution time	Memory
77547		szawinis	Port Facility (JOI17_port_facility)	C++17	0 / 100	61 ms	53880 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 l < rhs.l; }
	bool operator==(const seg& rhs) const {
		if(l == rhs.l) {
			assert(i == rhs.i);
			return true;
		}
		return false;
	}
};

pair<seg, seg> merge(pair<seg, seg> a, pair<seg, seg> b) {
	seg mn1 = seg(), mn2 = seg();
	mn1 = min(a.first, b.first);
	if(mn1 == a.first) mn2 = min(a.second, min(b.first, b.second));
	else mn2 = min(b.second, min(a.first, a.second));
	return make_pair(mn1, mn2);
}

int n;
vector<seg> a;
pair<seg, seg> t[N << 1];

void update(int i, seg v) {
	i += N;
	t[i] = merge({v, seg()}, t[i]);
	while(i >>= 1) t[i] = merge(t[i << 1], t[i << 1 | 1]);
}

pair<seg, seg> query(int l, int r) {
	pair<seg, seg> ret = {seg(), seg()};
	for(l += N, r += N+1; l < r; l >>= 1, r >>= 1) {
		if(l & 1) ret = merge(t[l++], ret);
		if(r & 1) ret = merge(t[--r], ret);
	}
	return ret;
}

int dsu[N];
int root(int v) { return (dsu[v] < 0 ? v : dsu[v] = root(dsu[v])); }

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);
	}
	for(int i = 1; i < 2*N; i++) t[i] = {seg(), seg()};
	sort(a.begin(), a.end(), [] (auto x, auto y) { return x.r < y.r; });
	fill(dsu, dsu+N, -1);
	for(seg s: a) {
		auto res = query(s.l+1, s.r-1);
		// cout << s.l << ' ' << s.r << " pair res" << res.first.l << ' ' << res.second.l << endl;
		if(res.second.l < s.l) cout << 0, exit(0);
		update(s.r, s);

		int u = s.i, v = res.first.i;
		if(v != MOD && res.first.l < s.l && (u = root(u)) != (v = root(v))) {
			dsu[u] += dsu[v];
			dsu[v] = u;		
		}
	}
	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