Submission #543068

#	Time	Username	Problem	Language	Result	Execution time	Memory
543068		S920105123	Port Facility (JOI17_port_facility)	C++14	100 / 100	5893 ms	1047760 KiB

port_facility

#include <bits/stdc++.h>
#define LL long long
#define PII pair<int, int>
const LL MOD = (LL) 1e9 + 7;
const int MAXN = 2000005;
using namespace std;
 
struct Interval {
	int l, r;
};
 
int n, col[MAXN];
vector<PII> G[MAXN];
Interval I[MAXN];
 
void add_edge(int u, int v, int w) {
	G[u].push_back(PII(v, w));
	G[v].push_back(PII(u, w));
}
 
struct Segment_tree {
	vector<int> ps[4*MAXN];
	void add_point(int q, int id, int l, int r, int idx) {
		while (1) {
			ps[idx].push_back(id);
			if (l == r) break;
			int mid = (l + r) / 2;
			if (q <= mid) {
				r = mid;
				idx <<= 1;
			}
			else {
				l = mid + 1;
				idx = idx << 1 | 1;
			}
		}
	}
	void find_all(int ql, int qr, int id, int l, int r, int idx) {
		if (ql <= l && r <= qr) {
			for (int v : ps[idx]) {
				add_edge(v, id, 1);
			}
			if (!ps[idx].empty()) {
				ps[idx].resize(1);
			}
			return;
		}
		int mid = (l + r) >> 1;
		if (ql <= mid) {
			find_all(ql, qr, id, l, mid, idx << 1);
		}
		if (qr > mid) {
			find_all(ql, qr, id, mid + 1, r, idx << 1 | 1);
		}
	}
} tree;
 
int dfs(int v, int c) {
	int ok = 1;
	col[v] = c;
	for (PII p : G[v]) {
		int to = p.first, w = p.second;
		if (col[to] == -1) {
			ok &= dfs(to, c ^ w);
		}
		else {
			ok &= ((col[to] ^ col[v]) == w);
		}
	}
	return ok;
}
 
void solve() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> I[i].l >> I[i].r;
	}
	sort(I + 1, I + 1 + n, [&] (Interval a, Interval b) {
		return a.l < b.l;
	});
	
	int m = 2 * n;
	for (int i = 1; i <= n; i++) {
		int l = I[i].l, r = I[i].r;
		tree.find_all(l, r, i, 1, m, 1);
		tree.add_point(r, i, 1, m, 1);
	}
	
	int cc = 0;
	fill(col + 1, col + 1 + n, -1);
	for (int i = 1; i <= n; i++) {
		if (col[i] == -1) {
			if (!dfs(i, 0)) {
				cout << "0\n";
				return;
			}
			cc++;
		}
	}
	LL ans = 1;
	for (int i = 0; i < cc; 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