Submission #1225431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225431		siewjh	Port Facility (JOI17_port_facility)	C++20	10 / 100	3 ms	4424 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;
int fw[MAXN2], p[MAXN], rnk[MAXN];
int N, N2, cc;
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);
}
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 root(int x){
	if (p[x] == -1) return x;
	else return p[x] = root(p[x]);
}
void join(int a, int b){
	int ra = root(a), rb = root(b);
	if (ra == rb) return;
	cc--;
	if (rnk[ra] > rnk[rb]) swap(ra, rb);
	p[ra] = rb;
	if (rnk[ra] == rnk[rb]) rnk[rb]++;
}
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));
	cc = N;
	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) join(i, pid);
			}
			else if (l < pr){
				if (rquery(l, pr) != 0){
					cout << 0; return 0;
				}
				join(i, pid); break;
			}
			else break;
		}
		st.push_back({l, r, i});
	}
	cout << pwr(2, cc);
}

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