Submission #168684

#	Time	Username	Problem	Language	Result	Execution time	Memory
168684		maruii	Port Facility (JOI17_port_facility)	C++14	0 / 100	91 ms	98808 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define ff first
#define ss second

const int mod = 1e9 + 7;
int mp(int x, int a) {
	if (a == 0) return 1;
	int ret = mp(x, a >> 1);
	if (a & 1) return 1ll * ret * ret % mod * x % mod;
	return 1ll * ret * ret % mod;
}

int N;
pii P[1000005];

const int SIZE = 1 << 20;
struct ST {
	set<int> A[2 * SIZE];
	void insert(int x, int v) {
		for (x += SIZE; x; x >>= 1) A[x].insert(v);
	}
	void erase(int x, int v) {
		for (x += SIZE; x; x >>= 1) A[x].erase(v);
	}
	vector<int> query(int s, int e, int a, int b) {
		vector<int> ret;
		for (s += SIZE, e += SIZE; s <= e; s >>= 1, e >>= 1) {
			if ( s & 1) {
				auto i = A[s].lower_bound(a);
				auto j = A[s].lower_bound(b);
				for (; i != j; ++i) ret.push_back(*i);
				s++;
			}
			if (~e & 1) {
				auto i = A[e].lower_bound(a);
				auto j = A[e].lower_bound(b);
				for (; i != j; ++i) ret.push_back(*i);
				e--;
			}
		}
		return ret;
	}
} seg;

bool vis[1000005], C[1000005];
vector<int> A, B;
void dfs(int x) {
	if (C[x]) A.push_back(x);
	else B.push_back(x);
	vis[x] = 1;
	auto v = seg.query(P[x].ff, P[x].ss, 0, x);
	auto u = seg.query(P[x].ss, 2 * N, x, N);
	for (auto i : v) seg.erase(P[i].ss, i);
	for (auto i : u) seg.erase(P[i].ss, i);
	for (auto i : v) C[i] = C[x] ^ 1, dfs(i);
	for (auto i : u) C[i] = C[x] ^ 1, dfs(i);
}

int main() {
	cin >> N;
	for (int i = 0; i < N; ++i) {
		int a, b; cin >> a >> b;
		P[i] = {a, b};
	}
	sort(P, P + N);
	for (int i = 0; i < N; ++i) seg.insert(P[i].ss, i);
	int cnt = 0;
	for (int i = N - 1; i >= 0; --i) {
		if (vis[i]) continue;
		cnt++;
		seg.erase(P[i].ss, i);
		dfs(i);
	}
	priority_queue<int, vector<int>, greater<int> > pq;
	sort(A.begin(), A.end());
	sort(B.begin(), B.end());
	for (auto i : A) {
		while (pq.size() && pq.top() < P[i].ff) pq.pop();
		if (pq.size() && pq.top() < P[i].ss) return !printf("0");
		pq.push(P[i].ss);
	}
	while (pq.size()) pq.pop();
	for (auto i : B) {
		while (pq.size() && pq.top() < P[i].ff) pq.pop();
		if (pq.size() && pq.top() < P[i].ss) return !printf("0");
		pq.push(P[i].ss);
	}
	cout << mp(2, cnt);
	return 0;
}

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