Submission #131667

#	Time	Username	Problem	Language	Result	Execution time	Memory
131667		onjo0127	Port Facility (JOI17_port_facility)	C++11	Compilation error	0 ms	0 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;

const int MOD = 1e9 + 7, INF = 1e9;
int N, A[1000009], B[1000009], C[1000009];
pii LA[1000009], RA[1000009];

struct segtree {
	pii T[5000009];
	void init(pii A[], int idx, int s, int e) {
		if(s == e) {
			T[idx] = A[s];
			return;
		}
		int m = s+e >> 1;
		init(A, idx*2, s, m);
		init(A, idx*2+1, m+1, e);
		T[idx] = max(T[idx*2], T[idx*2+1]);
	}
	void upd(int idx, int s, int e, int p, pii v) {
		if(p < s || e < p) return;
		if(s == e) {
			T[idx] = v;
			return;
		}
		int m = s+e >> 1;
		upd(idx*2, s, m, p, v);
		upd(idx*2+1, m+1, e, p, v);
		T[idx] = max(T[idx*2], T[idx*2+1]);
	}
	pii get(int idx, int s, int e, int l, int r) {
		if(r < s || e < l) return {-INF, -1};
		if(l <= s && e <= r) return T[idx];
		int m = s+e >> 1;
		return max(get(idx*2, s, m, l, r), get(idx*2+1, m+1, e, l, r));
	}
} LS, RS;

void dfs(int x, int c) {
	C[x] = c;
	RS.upd(1, 1, 2*N, A[x], {-INF, x});
	LS.upd(1, 1, 2*N, B[x], {-INF, x});
	while(1) {
		int lm, rm, id; tie(rm, id) = RS.get(1, 1, 2*N, A[x] + 1, B[x] - 1);
		if(rm > B[x]) {
			dfs(id, 3 - c);
			continue;
		}
		tie(lm, id) = LS.get(1, 1, 2*N, A[x] + 1, B[x] - 1); lm = -lm;
		if(lm < A[x]) {
			dfs(id, 3 - c);
			continue;
		}
		break;
	}
}

bool chk(vector<pii> S) {
	sort(S.begin(), S.end());
	vector<int> T;
	for(auto& it: S) {
		while(T.size() && T.back() < it.first) T.pop_back();
		if(T.size() && T.back() < it.second) return false;
		T.push_back(it.second);
	}
	return true;
}

int main() {
	scanf("%d",&N);
	for(int i=1; i<=2*N; i++) LA[i] = RA[i] = {-INF, -1};
	for(int i=1; i<=N; i++) {
		scanf("%d%d",&A[i],&B[i]);
		RA[A[i]] = {B[i], i};
		LA[B[i]] = {-A[i], i};
	}
	LS.init(LA, 1, 1, 2*N); RS.init(RA, 1, 1, 2*N);
	int ans = 1;
	for(int i=1; i<=N; i++) if(!C[i]) {
		dfs(i, 1);
		ans *= 2; ans %= MOD;
	}
	vector<pii> AS, BS;
	for(int i=1; i<=N; i++) {
		if(C[i] == 1) AS.push_back({A[i], B[i]});
		if(C[i] == 2) BS.push_back({A[i], B[i]});
	}
	if(!chk(AS) || !chk(BS)) return !printf("0");
	printf("%d", ans);
	return 0;
}

Compilation message (stderr)

Compilation timeout while compiling port_facility