This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// 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 NN=5e7+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;
}
# | 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... |