Submission #953474

#	Time	Username	Problem	Language	Result	Execution time	Memory
953474		pcc	Port Facility (JOI17_port_facility)	C++17	100 / 100	1684 ms	189980 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second
#define ll long long

const ll mod = 1e9+7;
const int mxn = 2e6+10;

ll pw(ll a,ll b){
	ll re = 1;
	while(b){
		if(b&1)re = re*a%mod;
		b>>=1;
		a = a*a%mod;
	}
	return re;
}
ll mad(ll a,ll b){
	a += b;
	return a>=mod?a-mod:a;
}


void print(priority_queue<pii,vector<pii>,less<pii>> pq){
	vector<pii> tmp;
	while(!pq.empty()){
		cerr<<pq.top().fs<<','<<pq.top().sc<<' ';
		tmp.push_back(pq.top());
		pq.pop();
	}
	cerr<<endl;
	return;
}

struct DSU{
	int dsu[mxn],sz[mxn];
	priority_queue<pii,vector<pii>,less<pii>> pq[mxn];
	DSU(){}
	void init(int n){
		for(int i = 0;i<=n;i++)dsu[i] = i,sz[i] = 1;
		return;
	}
	int root(int k){
		return k == dsu[k]?k:dsu[k] = root(dsu[k]);
	}
	void onion(int a,int b){
		a = root(a),b = root(b);
		if(a == b)return;
		if(sz[a]<sz[b])swap(a,b);
		dsu[b] = a;
		sz[a] += sz[b];
		if(pq[a].size()<pq[b].size())pq[a].swap(pq[b]);
		while(!pq[b].empty()){
			pq[a].push(pq[b].top());
			pq[b].pop();
		}
		return;
	}
};

pii arr[mxn];
int N;
int C = 0;
int col[mxn];
DSU dsu;
int op[mxn];
set<pii> st;
bitset<mxn> active;

void update(int r){
	r = dsu.root(r);
	if(!dsu.pq[r].empty()&&st.find(dsu.pq[r].top()) != st.end())st.erase(dsu.pq[r].top());
	while(!dsu.pq[r].empty()&&!active[dsu.pq[r].top().sc])dsu.pq[r].pop();
	if(!dsu.pq[r].empty())st.insert(dsu.pq[r].top());
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N;
	dsu.init(N*2);
	for(int i = 1;i<=N;i++){
		cin>>arr[i].fs>>arr[i].sc;
		op[arr[i].fs] = i;
		op[arr[i].sc] = -i;
		dsu.pq[i*2].push(pii(arr[i].fs,i));
	}

	for(int i = 1;i<=N*2;i++){
		if(op[i]>0){
			active[op[i]] = true;
			update(op[i]*2);
			continue;
		}
		int pos = -op[i];
		active[pos] = false;
		update(dsu.root(pos*2));
		while(!st.empty()&&st.rbegin()->fs>arr[pos].fs){
			if(active[st.rbegin()->sc]){
				dsu.onion(pos*2-1,st.rbegin()->sc*2);
				dsu.onion(pos*2,st.rbegin()->sc*2-1);
			}
			st.erase(*st.rbegin());
		}
		update(dsu.root(pos*2-1));
		//cerr<<i<<":";for(auto &j:st)cerr<<j.fs<<','<<j.sc<<' ';cerr<<endl;
	}

	int ans = 0;
	for(int i = 1;i<=N;i++){
		if(dsu.root(i*2) == dsu.root(i*2-1)){
			cout<<0;
			return 0;
		}
		if(dsu.root(i*2) == i*2)ans++;
		if(dsu.root(i*2-1) == i*2-1)ans++;
	}
	cout<<pw(2,ans>>1);
}

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