Submission #168709

#	Time	Username	Problem	Language	Result	Execution time	Memory
168709		maruii	Port Facility (JOI17_port_facility)	C++14	100 / 100	2764 ms	258860 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];
int idx[2000005];

const int SIZE = 1 << 21;
struct ST {
	vector<pii> A;
	ST() { A.resize(2 * SIZE); }
	void update(int x, int v) {
		x += SIZE;
		A[x] = {v, x - SIZE};
		for (x >>= 1; x; x >>= 1) A[x] = max(A[x << 1], A[x << 1 | 1]);
	}
	pii query(int s, int e) {
		pii ret = {0, 0};
		for (s += SIZE, e += SIZE; s <= e; s >>= 1, e >>= 1) {
			if ( s & 1) ret = max(ret, A[s++]);
			if (~e & 1) ret = max(ret, A[e--]);
		}
		return ret;
	}
} seg1, seg2;

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;
	vector<int> v;
	while (1) {
		auto t = seg1.query(P[x].ff, P[x].ss);
		if (2 * N + 1 - t.ff > P[x].ff) break;
		seg1.update(t.ss, 0);
		seg2.update(2 * N + 1 - t.ff, 0);
		v.push_back(idx[2 * N + 1 - t.ff]);
	}
	while (1) {
		auto t = seg2.query(P[x].ff, P[x].ss);
		if (t.ff < P[x].ss) break;
		seg1.update(t.ff, 0);
		seg2.update(t.ss, 0);
		v.push_back(idx[t.ss]);
	}
	for (auto i : v) 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) seg1.update(P[i].ss, 2 * N + 1 - P[i].ff), seg2.update(P[i].ff, P[i].ss), idx[P[i].ff] = i;
	int cnt = 0;
	for (int i = N - 1; i >= 0; --i) {
		if (vis[i]) continue;
		cnt++;
		seg1.update(P[i].ss, 0);
		seg2.update(P[i].ff, 0);
		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;
}

Compilation message (stderr)

port_facility.cpp: In function 'int mp(int, int)':
port_facility.cpp:7:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  if (a == 0) return 1; int ret = mp(x, a >> 1); if (a & 1) return 1ll * ret * ret % mod * x % mod;
  ^~
port_facility.cpp:7:24: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  if (a == 0) return 1; int ret = mp(x, a >> 1); if (a & 1) return 1ll * ret * ret % mod * x % mod;
                        ^~~

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