제출 #531441

#제출 시각아이디문제언어결과실행 시간메모리
531441codr0Port Facility (JOI17_port_facility)C++14
100 / 100
4279 ms242848 KiB
// 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...