Submission #455148

#	Time	Username	Problem	Language	Result	Execution time	Memory
455148		S920105123	Port Facility (JOI17_port_facility)	C++14	0 / 100	18 ms	23740 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;
	}
};

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

void add_edge(int u, int v) {
//	cout << "Add " << u << ' ' << v << '\n';
	G[u].push_back(v);
	G[v].push_back(u);
}

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; i <= r; 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) {
			add_edge(I[ul].id, I[i].id);
			add[ul]++;
			add[ur - 1]--;
		}
	}
	for (int i = l; i <= r; i++) {
		if (i != l) {
			add[i] += add[i - 1];
		}
		if (add[i]) {
			add_edge(I[i].id, I[i + 1].id);
		}
	}
}

int dfs(int v, int c) {
	int ok = 1;
	col[v] = c;
	for (int to : G[v]) {
		if (col[to] == -1) {
			ok &= dfs(to, !c);
		}
		else {
			ok &= (col[v] != col[to]);
		}
	}
	return ok;
}

int check() {
	vector<int> stk[2];
	sort(I + 1, I + 1 + n, [&] (Interval a, Interval b) {
		return a.l < b.l;
	});
	for (int i = 1; i <= n; i++) {
//		cout << I[i].id << " -> " << col[I[i].id] << '\n';
		int c = col[I[i].id];
		while (!stk[c].empty() && stk[c].back() <= I[i].l) {
			stk[c].pop_back();
		}
//		cout << "Now " << stk[c].size() << '\n';
		if (!stk[c].empty() && I[i].r > stk[c].back()) {
			return 0;
		}
		stk[c].push_back(I[i].r);
	}
	return 1;
}

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;
	});
	solve2(1, n);
	
	int cnt = 0, ok = 1;
	fill(col + 1, col + 1 + n, -1);
	for (int i = 1; i <= n; i++) {
		if (col[i] == -1) {
			ok &= dfs(i, 0);
			cnt++;
		}
	}
	ok &= check();
	
	if (!ok) {
		cout << "0\n";
	}
	else {
		LL ans = 1;
		for (int i = 0; i < 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: 0 / 10
• Subtask 2: 0 / 12
• Subtask 3: 0 / 56
• Subtask 4: 0 / 22