Submission #1225465

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225465		siewjh	Port Facility (JOI17_port_facility)	C++20	100 / 100	418 ms	137432 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1000005;
const int MAXN2 = 2000005;
const ll mod = 1e9 + 7;
vector<pair<int, int>> adj[MAXN];
int fw[MAXN2], p[MAXN], rnk[MAXN], clr[MAXN];
int N, N2;
void update(int x, int v){
	for (; x <= N2; x += (x & -x)) fw[x] += v;
}
int query(int x){
	int res = 0;
	for (; x; x -= (x & -x)) res += fw[x];
	return res;
}
int rquery(int l, int r){
	return query(r) - query(l - 1);
}
void dfs(int x, int c){
	clr[x] = c;
	for (auto [nn, nc] : adj[x]){
		if (clr[nn] == -1) dfs(nn, c != nc);
		else if (clr[nn] != (c != nc)){
			cout << 0; exit(0);
		}
	}
}
ll pwr(ll a, ll b){
	ll res = 1;
	for (; b; b >>= 1){
		if (b & 1) res = res * a % mod;
		a = a * a % mod;
	}
	return res;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> N; N2 = N << 1;
	vector<pair<int, int>> vec(N);
	for (int i = 0; i < N; i++){
		int l, r; cin >> l >> r;
		vec[i] = {r, l};
	}
	for (int i = 1; i <= N2; i++) update(i, 1);
	sort(vec.begin(), vec.end());
	vector<tuple<int, int, int>> st;
	memset(p, -1, sizeof(p)); memset(clr, -1, sizeof(clr));
	for (int i = 0; i < N; i++){
		int l, r; tie(r, l) = vec[i];
		update(l, -1); update(r, -1);
		while (!st.empty()){
			int pl, pr, pid; tie(pl, pr, pid) = st.back();
			if (l < pl){
				st.pop_back();
				if (rquery(pl, pr) != 0){
					adj[i].push_back({pid, 0}); adj[pid].push_back({i, 0});
				}
			}
			else if (l < pr){
				if (rquery(l, pr) != 0){
					cout << 0; return 0;
				}
				adj[i].push_back({pid, 1}); adj[pid].push_back({i, 1}); break;
			}
			else break;
		}
		st.push_back({l, r, i});
	}
	int cc = 0;
	for (int i = 0; i < N; i++)
		if (clr[i] == -1){
			dfs(i, 0); cc++;
		}
	cout << pwr(2, cc);
}

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