Submission #655968

#	Time	Username	Problem	Language	Result	Execution time	Memory
655968		Mohammad_Parsa	Port Facility (JOI17_port_facility)	C++14	0 / 100	0 ms	340 KiB

port_facility

/* 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;
}

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