Submission #655933

#	Time	Username	Problem	Language	Result	Execution time	Memory
655933		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];
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;
				it--;
				for(;it!=st.begin();){
					int g=it->S;
					z[g]=min(z[g],1);
					it--;
					if(g>it->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