Submission #531441

#	Time	Username	Problem	Language	Result	Execution time	Memory
531441		codr0	Port Facility (JOI17_port_facility)	C++14	100 / 100	4279 ms	242848 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=2e6+4;
pii seg_st[4*N];
pii seg_en[4*N];
int st[N],en[N],n;
bool mark[N];
vector<int> adj[N];
vector<int> V[2];
 
	bool check(bool X){
		vector<int> vc=V[X];
		vector<pii> pi;
		for(int x0:vc) pi.pb({st[x0],en[x0]});
		sort(all(pi));
		set<pii> enst;
		FOR(i,0,SZ(pi)-1){
			while(1){
				if(enst.empty()) break;
				pii x0=*(enst.begin());
				if(x0.F<pi[i].F){
					enst.erase({x0.F,x0.S});
				}else break;
			}
			if(!enst.empty()&&(*enst.begin()).F<pi[i].S) return 0;
			enst.insert({pi[i].S,pi[i].F});
		}
		return 1;
	}

	void build(int id,int l,int r){
		seg_en[id]={MOD,MOD};
		if(l+1==r) return;
		int mid=(r+l)/2;
		build(2*id,l,mid);
		build(2*id+1,mid,r);
	}

	pii get_en(int id,int l,int r,int st,int en){
		if(st>=r||en<=l) return {MOD,MOD};
		if(st<=l&&en>=r) return seg_en[id];
		int mid=(r+l)/2;
		return min(get_en(2*id,l,mid,st,en),get_en(2*id+1,mid,r,st,en));
	}

	pii get_st(int id,int l,int r,int st,int en){
		if(st>=r||en<=l) return {0,0};
		if(st<=l&&en>=r) return seg_st[id];
		int mid=(r+l)/2;
		return max(get_st(2*id,l,mid,st,en),get_st(2*id+1,mid,r,st,en));
	}

	void upd_st(int id,int l,int r,int ind,pii x0){
		if(ind>=r||ind<l) return;
		if(l+1==r){
			seg_st[id]=x0;
			return;
		}
		int mid=(r+l)/2;
		upd_st(2*id,l,mid,ind,x0);
		upd_st(2*id+1,mid,r,ind,x0);
		seg_st[id]=max(seg_st[2*id],seg_st[2*id+1]);
	}

	void upd_en(int id,int l,int r,int ind,pii x0){
		if(ind>=r||ind<l) return;
		if(l+1==r){
			seg_en[id]=x0;
			return;
		}
		int mid=(r+l)/2;
		upd_en(2*id,l,mid,ind,x0);
		upd_en(2*id+1,mid,r,ind,x0);
		seg_en[id]=min(seg_en[2*id],seg_en[2*id+1]);
	}

	void rm(int i){
		upd_en(1,1,2*n+1,en[i],{MOD,MOD});
		upd_st(1,1,2*n+1,st[i],{0,0});
	}

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

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

	cin>>n;
	build(1,1,2*n+1);
	FOR(i,1,n){
		cin>>st[i]>>en[i];
		upd_en(1,1,2*n+1,en[i],{st[i],i});
		upd_st(1,1,2*n+1,st[i],{en[i],i});
	}
	deque<int> dq;
	int C=0;
	FOR(i,1,n){
		if(mark[i]) continue;
		C++;
		mark[i]=1;
		rm(i);
		dq.pb(i);
		while(!dq.empty()){
			int v=dq.front();
			dq.pop_front();
			while(1){
				pii x0=get_st(1,1,2*n+1,st[v],en[v]+1);
				if(x0.F>en[v]){
					mark[x0.S]=1;
					rm(x0.S);
					adj[v].pb(x0.S);
					adj[x0.S].pb(v);
					dq.pb(x0.S);
				}else break;
			}
			while(1){
				pii x0=get_en(1,1,2*n+1,st[v],en[v]+1);
				if(x0.F<st[v]){
					mark[x0.S]=1;
					rm(x0.S);
					adj[v].pb(x0.S);
					adj[x0.S].pb(v);
					dq.pb(x0.S);
				}else break;
			}
		}
	}
	FOR(i,1,n) mark[i]=0;
	int ans=1;
	FOR(i,1,C) ans=(1LL*ans*2)%MOD;
	FOR(i,1,n){
		if(mark[i]) continue;
		V[0].clear();
		V[1].clear();
		dfs(i,0);
		if(!check(1)||!check(0)) return cout<<"0\n",0;
	}
	cout<<ans<<'\n';

	return 0;
	}

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