Submission #655968

#TimeUsernameProblemLanguageResultExecution timeMemory
655968Mohammad_ParsaPort Facility (JOI17_port_facility)C++14
0 / 100
0 ms340 KiB
/* in the name of allah */
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define F first
#define S second
#define mk make_pair

const int N=2e6+7,mod=1e9+7;
int z[N],s[N],e[N],p[N];
set<pair<int,int>> st;

int main(){
	ios:: sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int n,x,y;
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>x>>y;
		e[x]=y;
		s[y]=x;
	}
	for(int i=1;i<=2*n;i++){
		if(e[i]){
			st.insert(mk(e[i],i));
			auto it=st.find(mk(e[i],i));
			if(it==st.begin()) z[i]=2;
			else{
				z[i]=1;
				auto it2=st.begin();
				it--;
				for(;it2!=it;){
					int g=it2->S;
					z[g]=min(z[g],1);
					it2++;
					if(p[g] && p[g]!=(it2->S)) z[i]=0;
					p[g]=(it2->S);
					if(g<(it2->S)) z[i]=0;
				}
			}
		}
		else{
			st.erase(mk(i,s[i]));
		}
	}
	ll ans=1;
	for(int i=1;i<=2*n;i++){
		if(e[i]) ans=ans*(ll)z[i]%mod;
	}
	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...