이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// 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=1e6+4;
const int N2=5e6+1e6;
const int NN=5e7+1e6;
int aX[NN],bX[NN],cX[NN],dX[NN];
vector<int> adj[N2];
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |