Submission #529167

#	Time	Username	Problem	Language	Result	Execution time	Memory
529167		codr0	Port Facility (JOI17_port_facility)	C++14	78 / 100	1471 ms	498704 KiB

port_facility

// Code by Parsa Eslami
 
#include <bits/stdc++.h>
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORR(i,a,b) for(int i=a;i>=b;i--)
#define S second
#define F first
#define pb push_back
#define SZ(x) (int)x.size()
#define all(x) x.begin(),x.end()
#define err(x) cout<<#x<<": "<<x<<'\n';
 
using namespace std;
const int MOD=1e9+7;
const int N=1e5+4;
const int NN=5e6+1e6;
vector<int> adj[NN];
bool mark[NN];
int n;
int go[10*N],st[N],en[N];
int ver;
vector<int> vc[2];

	void build(int id,int l,int r){
		go[id+N]=id+N;
		go[id+5*N]=id+5*N;
		if(l+1==r) return;
		int mid=(r+l)/2;
		adj[id+N].pb(2*id+N);
		adj[id+N].pb(2*id+N+1);
		adj[2*id+5*N+1].pb(id);
		adj[2*id+5*N].pb(id);
		build(2*id,l,mid);
		build(2*id+1,mid,r);
	}

	void cng_get(int id,int l,int r,int ind,int v){//N up to down
		if(ind>=r||ind<l) return;
		ver++;
		adj[ver].pb(go[id+N]);
		go[id+N]=ver;
		if(l+1==r){
			adj[go[id+N]].pb(v);
			return;
		}
		int mid=(r+l)/2;
		cng_get(2*id,l,mid,ind,v);
		cng_get(2*id+1,mid,r,ind,v);
		if(ind<mid){
			adj[go[id+N]].pb(go[2*id+N]);
		}else{
			adj[go[id+N]].pb(go[2*id+1+N]);
		}
	}

	void cng_give(int id,int l,int r,int ind,int v){//5*N down to up
		if(ind>=r||ind<l) return;
		ver++;
		adj[go[id+5*N]].pb(ver);
		go[id+5*N]=ver;
		if(l+1==r){
			adj[v].pb(go[id+5*N]);
			return;
		}
		int mid=(r+l)/2;
		cng_give(2*id,l,mid,ind,v);
		cng_give(2*id+1,mid,r,ind,v);
		if(ind<mid){
			adj[go[2*id+5*N]].pb(go[id+5*N]);
		}else{
			adj[go[2*id+1+5*N]].pb(go[id+5*N]);
		}
	}

	void get(int id,int l,int r,int st,int en,int v){//5*N down to up
		if(st>=r||en<=l) return;
		if(st<=l&&en>=r){
			adj[go[id+5*N]].pb(v);
			return;
		}
		int mid=(r+l)/2;
		get(2*id,l,mid,st,en,v);
		get(2*id+1,mid,r,st,en,v);
	}

	void give(int id,int l,int r,int st,int en,int v){//N up to down
		if(st>=r||en<=l) return;
		if(st<=l&&en>=r){
			adj[v].pb(go[id+N]);
			return;
		}
		int mid=(r+l)/2;
		give(2*id,l,mid,st,en,v);
		give(2*id+1,mid,r,st,en,v);
	}

	void dfs(int v,bool X){
		if(v<=n) {
			X=!X;
			vc[X].pb(v);
		}
		mark[v]=1;
		for(int u:adj[v]) if(!mark[u]) dfs(u,X);
	}

	bool check(bool x0){
		vector<int> V=vc[x0];
		sort(all(V));
		set<int> ST;
		ST.insert(3*N);
		for(int id:V){
			if((*ST.lower_bound(st[id]))!=(*ST.lower_bound(en[id]))) return 0;
			ST.insert(en[id]);
		}
		return 1;
	}

	int32_t main(){
	ios_base::sync_with_stdio(0); cin.tie(0);	

	cin>>n;
	ver=9*N+1e5;
	build(1,1,n+1);
	vector<int> E;
	vector<pii> B;
	FOR(i,1,n){
		int st,en; cin>>st>>en;
		E.pb(en);
		B.pb({st,en});
	}
	sort(all(B));
	sort(all(E));
	FOR(i,0,n-1){
		st[i+1]=B[i].F;
		en[i+1]=B[i].S;
	}
	FOR(i,0,n-1){
		int st=lower_bound(all(E),B[i].F)-E.begin()+1;
		int en=lower_bound(all(E),B[i].S)-E.begin()+1;
		get(1,1,n+1,st,en+1,i+1);
		give(1,1,n+1,st,en+1,i+1);
		cng_get(1,1,n+1,en,i+1);
		cng_give(1,1,n+1,en,i+1);
	}
	int ans=1;
	FOR(i,1,n) if(!mark[i]){
		ans=(1LL*ans*2)%MOD;
		vc[1].clear();
		vc[0].clear();
		dfs(i,0);
		if((!check(1))||(!check(0))){
			cout<<"0\n";
			exit(0);
		}
	}
	cout<<ans<<'\n';

	return 0;
	}

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