Submission #1321707

#TimeUsernameProblemLanguageResultExecution timeMemory
1321707PieArmyPort Facility (JOI17_port_facility)C++20
0 / 100
4 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)

int n;
int arr[1000023],brr[1000023];
int per[1000023];
set<pair<int,int>>ed,st;
vector<int>komsu[1000023];
int vis[1000023];
int ans=1;

bool dfs(int pos){
	for(int x:komsu[pos]){
		if(vis[x]==vis[pos])return false;
		if(vis[x])continue;
		vis[x]=(vis[pos]^3);
		if(!dfs(x))return false;
	}
	return true;
}

signed main(){
	ios_base::sync_with_stdio(23^23);cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i]>>brr[i];
		per[i]=i;
	}
	sort(per+1,per+n+1,[&](const int &x,const int &y){
		return brr[x]<brr[y];
	});
	for(int i=1;i<=n;i++){
		st.insert({arr[i],i});
	}
	for(int i=1;i<=n;i++){
		st.erase({arr[per[i]],per[i]});
		while(true){
			auto itr=st.lower_bound({arr[per[i]],per[i]});
			if(itr==st.end())break;
			if(itr->fr>brr[per[i]])break;
			int a=per[i],b=itr->sc;
			st.erase(itr);
			komsu[a].pb(b);
			komsu[b].pb(a);
		}
	}
	sort(per+1,per+n+1,[&](const int &x,const int &y){
		return arr[x]>arr[y];
	});
	for(int i=1;i<=n;i++){
		st.insert({brr[i],i});
	}
	for(int i=1;i<=n;i++){
		st.erase({brr[per[i]],per[i]});
		while(true){
			auto itr=st.lower_bound({brr[per[i]],per[i]});
			if(itr==st.begin())break;
			itr--;
			if(itr->fr<arr[per[i]])break;
			int a=per[i],b=itr->sc;
			st.erase(itr);
			komsu[a].pb(b);
			komsu[b].pb(a);
		}
	}
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		vis[i]=1;
		if(!dfs(i)){
			ans=0;
		}
		ans=ans+ans;
		if(ans>=1000000007)ans-=1000000007;
	}
	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...