Submission #1322453

#TimeUsernameProblemLanguageResultExecution timeMemory
1322453PieArmyPort Facility (JOI17_port_facility)C++20
0 / 100
0 ms332 KiB
#include<bits/stdc++.h>
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
using namespace std;
#define mid ((left+right)>>1)

struct DSU{
	int n;
	vector<int>par,siz;
	void init(int N){
		n=N;
		par.resize(n+1);
		siz.resize(n+1,0);
		iota(par.begin(),par.end(),0);
	}
	int get(int x){
		if(x==par[x])return x;
		return par[x]=get(par[x]);
	}
	bool unite(int x,int y){
		x=get(abs(x));y=get(abs(y));
		if(x==y)return false;
		if(siz[x]<siz[y])swap(x,y);
		n--;
		siz[x]+=siz[y];
		par[y]=x;
		return true;
	}
};

int n;
int arr[2000023],pref[2000023],var[1000023];
pair<int,int>ara[1000023];
int ans=1;
DSU dsu;

void dnq(int left,int right){
	if(left==right)return;
	vector<int>v;
	for(int i=left;i<=right;i++){
		if(var[abs(arr[i])])continue;
		if(ara[abs(arr[i])].sc>right||ara[abs(arr[i])].fr<left)continue;
		v.pb(abs(arr[i]));
		var[v.back()]=1;
	}
	for(int x:v){
		if(ara[x].sc<=mid){
			var[x]=1;
		}
		if(ara[x].fr<=mid&&ara[x].sc>mid){
			var[x]=2;
		}
		if(ara[x].fr>mid){
			var[x]=3;
		}
	}
	{
		int mn=mid+1,mx=mid,las=-1;
		int r=mid;
		for(int l=mid;l>=left;l--){
			if(var[abs(arr[l])]!=2)continue;
			mx=max(mx,ara[abs(arr[l])].sc);
			if(las!=-1){
				dsu.unite(las,arr[l]);
			}
			las=abs(arr[l]);
			while(r<mx){
				r++;
				if(var[abs(arr[r])]!=2)continue;
				mn=min(mn,ara[abs(arr[r])].fr);
				dsu.unite(las,arr[r]);
			}
			if(l==mn)las=-1;
		}
	}
	vector<int>sira,dp;
	pref[mid+1]=-1;
	for(int i=mid;i>=left;i--){
		pref[i]=pref[i+1];
		if(var[abs(arr[i])]==2){
			sira.pb(abs(arr[i]));
			dp.pb(0);
			pref[i]++;
		}
	}
	for(int i=mid;i>=left;i--){
		if(arr[i]<0)continue;
		if(var[arr[i]]!=1)continue;
		int l=pref[ara[arr[i]].fr],r=pref[ara[arr[i]].sc];
		if(l==r)continue;
		r++;
		dsu.unite(sira[r],arr[i]);
		dp[r]++;
		dp[l]--;
	}
	int d=0;
	for(int i=0;i<sira.size();i++){
		if(d){
			dsu.unite(sira[i],sira[i-1]);
		}
		d+=dp[i];
	}

	sira.clear();dp.clear();
	pref[mid]=-1;
	for(int i=mid+1;i<=right;i++){
		pref[i]=pref[i-1];
		if(var[abs(arr[i])]==2){
			sira.pb(abs(arr[i]));
			dp.pb(0);
			pref[i]++;
		}
	}
	for(int i=mid+1;i<=right;i++){
		if(arr[i]<0)continue;
		if(var[arr[i]]!=3)continue;
		int l=pref[ara[arr[i]].fr],r=pref[ara[arr[i]].sc];
		if(l==r)continue;
		l++;
		dsu.unite(sira[l],arr[i]);
		dp[l]++;
		dp[r]--;
	}
	d=0;
	for(int i=0;i<sira.size();i++){
		if(d){
			dsu.unite(sira[i],sira[i-1]);
		}
		d+=dp[i];
	}
	for(int x:v){
		var[x]=0;
	}
	dnq(left,mid);dnq(mid+1,right);
}

signed main(){
	ios_base::sync_with_stdio(23^23);cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>ara[i].fr>>ara[i].sc;
		arr[ara[i].fr]=-i;
		arr[ara[i].sc]=i;
	}
	set<pair<int,int>>st;
	set<int>bad;
	st.insert({0,2*n+1});
	st.insert({2*n+1,0});
	for(int i=1;i<=2*n;i++){
		if(arr[i]>0)continue;
		int l=ara[-arr[i]].fr,r=ara[-arr[i]].sc;
		if(st.upper_bound({l,0})->fr<(--st.upper_bound({r,0}))->fr){
			auto itr=bad.upper_bound(l);
			if(itr!=bad.end()&&*itr<r){
				ans=0;
				break;
			}
		}
		auto nex=st.upper_bound({r,0});
		auto pre=--st.upper_bound({r,0});
		if(pre->sc<nex->sc)bad.erase(nex->fr);
		if(pre->sc<l)bad.insert(r);
		if(l<nex->sc)bad.insert(nex->fr);
		st.insert({r,l});
	}
	if(!ans){
		cout<<ans<<endl;
		return 0;
	}
	dsu.init(n);
	dnq(1,2*n);
	for(int i=0;i<dsu.n;i++){
		ans*=2;
		if(ans>=1e9+7)ans-=1e9+7;
	}
	cout<<ans<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...