Submission #456413

#	Time	Username	Problem	Language	Result	Execution time	Memory
456413		S920105123	Port Facility (JOI17_port_facility)	C++14	78 / 100	6135 ms	1048576 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 id, int to, int w) {
//	cout << "Add " << id << ' ' << to << ' ' << w << '\n';
	G[id].push_back(PII(to, w));
	G[to].push_back(PII(id, w));
}

struct Segment_tree {
	int cov[4*MAXN];
	vector<int> ps[4*MAXN];
	void add_point(int q, int id, int l, int r, int idx) {
		ps[idx].push_back(id);
		if (l == r) {
			return;
		}
		int mid = (l + r) >> 1;
		if (q <= mid) {
			add_point(q, id, l, mid, idx << 1);
		}
		else {
			add_point(q, id, mid + 1, r, idx << 1 | 1);
		}
	}
	void find_all(int ql, int qr, int id, int l, int r, int idx) {
		if (ql <= l && r <= qr) {
			if (cov[idx] != 0) {
				int to = cov[idx];
				add_edge(id, to, 0);
			}
			else if (!ps[idx].empty()) {
				cov[idx] = id;
			}
			for (int to : ps[idx]) {
				add_edge(id, to, 1);
			}
			ps[idx].clear();
			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: 0 / 22