Submission #513687

#	Time	Username	Problem	Language	Result	Execution time	Memory
513687		Koosha_mv	Port Facility (JOI17_port_facility)	C++14	100 / 100	1471 ms	90000 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first

const int N=4e6+99,mod=1e9+7;

int n,m,ans=1,s[N],t[N],vis[N],mark[N],dist[N],segmx[N<<2],segmn[N<<2],tad[N],ted[N];
// mn : s mx : t
void updmn(int id){
	segmn[id]=min(segmn[id<<1],segmn[id<<1|1]);
}
void updmx(int id){
	segmx[id]=max(segmx[id<<1],segmx[id<<1|1]);
}
void add(int x){
	int id;
	id=t[x]+m;
	segmn[id]=s[x];
	id/=2;
	for(;id>0;id/=2){
		updmn(id);
	}
	id=s[x]+m;
	segmx[id]=t[x];
	id/=2;
	for(;id>0;id/=2){
		updmx(id);
	}
}
void del(int x){
	int id;
	id=t[x]+m;
	segmn[id]=s[0];
	id/=2;
	for(;id>0;id/=2){
		updmn(id);
	}
	id=s[x]+m;
	segmx[id]=t[0];
	id/=2;
	for(;id>0;id/=2){
		updmx(id);
	}
}
int getmn(int l, int r){
	int res=N+N;
	for (l += m, r += m; l < r; l >>= 1, r >>= 1) {
		if (l&1){
			minm(res,segmn[l++]);
		}
		if (r&1){
			minm(res,segmn[--r]);
		}
	}
	return res;
}
int getmx(int l, int r){
	int res=0;
	for (l += m, r += m; l < r; l >>= 1, r >>= 1) {
		if (l&1){
			maxm(res,segmx[l++]);
		}
		if (r&1){
			maxm(res,segmx[--r]);
		}
	}
	return res;
}
void bfs(int x){
	queue<int> q;
	q.push(x);
	vis[x]=1;
	del(x);
	while(q.size()){
		int u=q.front();
		//eror(u);
		q.pop();
		vis[u]=1;
		while(getmn(s[u],t[u])<s[u]){
			int v=mark[getmn(s[u],t[u])];
			dist[v]=dist[u]^1;
			q.push(v);
			del(v);
			//eror(v);
		}
		while(t[u]<getmx(s[u],t[u])){
			int v=mark[getmx(s[u],t[u])];
			dist[v]=dist[u]^1;
			q.push(v);
			del(v);
			//eror(v);
		}
	}	
	ans=2ll*ans%mod;
}
void check(){
	f(b,0,2){
		fill(tad,tad+N,0);
		fill(ted,ted+N,0);
		f(i,1,n+1){
			if(dist[i]==b){
				tad[s[i]]=i;
				ted[t[i]]=i;
			}
		}
		vector<int> v;
		f(i,1,2*n+1){
			//dbgv(v);
			if(tad[i]){
				v.pb(tad[i]);
			}
			if(ted[i]){
				if(ted[i]!=v.back()){
					cout<<0;
					exit(0);
				}
				v.pop_back();
			}
		}
	}	
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	fill(segmn,segmn+N,N);
	s[0]=N;
	cin>>n; m=2*n+10;
	f(i,1,n+1){
		cin>>s[i]>>t[i];
		mark[s[i]]=i;
		mark[t[i]]=i;
		add(i);
	}
	f(i,1,n+1){
		if(!vis[i]){
			bfs(i);
		}
	}
	check();
	cout<<ans;
}

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