Submission #455185

#	Time	Username	Problem	Language	Result	Execution time	Memory
455185		S920105123	Port Facility (JOI17_port_facility)	C++14	100 / 100	4106 ms	65864 KiB

port_facility

#include <bits/stdc++.h>
#define LL long long
const LL MOD = (LL) 1e9 + 7;
const int MAXN = 1000005;
using namespace std;

struct Interval {
	int l, r, id;
	bool operator < (const Interval &it) const {
		return r < it.r;
	}
};

struct DSU {
	int pa[MAXN], sz[MAXN], chg[MAXN], cnt, good;
	void init(int n) {
		cnt = n;
		good = 1;
		for (int i = 1; i <= n; i++) {
			pa[i] = i;
			sz[i] = 1;
			chg[i] = 0;
		}
	}
	int find(int x) {
		return x == pa[x] ? x : find(pa[x]);
	}
	int get_color(int x) {
		return x == pa[x] ? chg[x] : get_color(pa[x]) ^ chg[x];
	}
	void add_constraint(int x, int y, int xor_val) {
		int rx = find(x), ry = find(y);
		int cx = get_color(x), cy = get_color(y);
		if (rx == ry) {
			good &= (cx ^ cy) == xor_val;
			return;
		}
		if (sz[rx] < sz[ry]) {
			swap(x, y); swap(rx, ry); swap(cx, cy);
		} 
		cnt--;
		pa[ry] = rx;
		sz[rx] += sz[ry];
		if ((cx ^ cy) != xor_val) {
			chg[ry] ^= 1;
		}
	}
	int satisfiable() {
		return good;
	}
} U;

int n, add[MAXN];
vector<int> G[MAXN];
Interval I[MAXN];

void solve2(int l, int r) {
	if (l == r) {
		return;
	}
	int mid = (l + r) / 2;
	solve2(l, mid);
	solve2(mid + 1, r);
	sort(I + l, I + mid + 1, [&] (Interval a, Interval b) {
		return a.r < b.r;
	});
	
	for (int i = l - 1; i <= r + 1; i++) {
		add[i] = 0;
	}
	for (int i = mid + 1; i <= r; i++) {
		int ul = lower_bound(I + l, I + mid + 1, (Interval){-1, I[i].l, -1}) - I;
		int ur = upper_bound(I + l, I + mid + 1, (Interval){-1, I[i].r, -1}) - I;
		if (ul != ur) {
			U.add_constraint(I[ul].id, I[i].id, 1);
			add[ul]++;
			add[ur - 1]--;
		}
	}
	for (int i = l; i <= mid; i++) {
		add[i] += add[i - 1];
		if (add[i]) {
			U.add_constraint(I[i].id, I[i + 1].id, 0);
		}
	}
	assert(add[mid] == 0);
}

void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> I[i].l >> I[i].r;
		I[i].id = i;
	}
	sort(I + 1, I + 1 + n, [&] (Interval a, Interval b) {
		return a.l < b.l;
	});
	U.init(n);
	solve2(1, n);
	
	if (!U.satisfiable()) {
		cout << "0\n";
	}
	else {
		LL ans = 1;
		for (int i = 0; i < U.cnt; i++) {
			ans = ans * 2 % MOD;
		}
		cout << ans << '\n';
	}
}

int main() {
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);

	int tc = 1;
//	cin >> tc;
	for (int i = 1; i <= tc; i++) {
		solve();
	}

	return 0;
}

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