This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define maxn 2500000
using namespace std;
struct treap {
treap *l,*r;
int val;
unsigned long long prior;
treap(int val,unsigned long long prior) {
this->l=NULL;
this->r=NULL;
this->val=val;
this->prior=prior;
}
};
unsigned long long seed=122837128964317283;
unsigned long long tot=0;
unsigned long long rng() {
tot+=seed;
return tot;
}
void split(treap* t,treap* &l,treap* &r,int x) {
if(t==NULL) {
l=r=NULL;
}
else {
if(t->val<x) {
split(t->r,t->r,r,x);
l=t;
}
else {
split(t->l,l,t->l,x);
r=t;
}
}
}
void join(treap* &t,treap* l,treap* r) {
if(l==NULL) t=r;
else {
if(r==NULL) t=l;
else {
if(l->prior>r->prior) {
join(l->r,l->r,r);
t=l;
}
else {
join(r->l,l,r->l);
t=r;
}
}
}
}
int left(treap* t) {
if(t->l==NULL) return t->val;
else return left(t->l);
}
void pop_left(treap* &t) {
if(t->l==NULL) {
t=t->r;
return;
}
else pop_left(t->l);
}
int n;
int a[maxn];
int b[maxn];
int par[maxn];
int ord[maxn];
vector<int> c[maxn];
int d[maxn];
bool vis[maxn];
void dfs(int u) {
vis[u]=true;
for(auto v:c[u]) {
if(!vis[v]) {
d[v]=d[u]^1;
dfs(v);
}
}
}
int act_c[4*maxn];
vector<int> cur_c;
treap* tq[maxn];
long long mod=1000000007;
int find_par(int u) {
if(par[u]==u) return u;
par[u]=find_par(par[u]);
return par[u];
}
void print_par() {
for(int i=1;i<=n;i++) {
cerr<<"par["<<i<<"]="<<par[i]<<endl;
}
}
void unite(int u,int v) {
par[u]=v;
if(left(tq[u])<left(tq[v])) {
treap *l,*r,*tmp,*rez;
split(tq[u],l,r,left(tq[v]));
join(tmp,l,tq[v]);
join(rez,tmp,r);
tq[v]=rez;
}
else {
treap *l,*r,*tmp,*rez;
split(tq[v],l,r,left(tq[u]));
join(tmp,l,tq[u]);
join(rez,tmp,r);
tq[v]=rez;
}
}
inline void clear(int id,int l,int r) {
if(act_c[id]==0) return;
if(l==r) {
cur_c.push_back(-ord[l]);
return;
}
act_c[id]=0;
int m=(l+r)/2;
clear(id*2+1,l,m);
clear(id*2+2,m+1,r);
}
inline void active(int id,int l,int r,int x,int y) {
if(x<=l && r<=y) {
clear(id,l,r);
return;
}
if(y<l || r<x) return;
int m=(l+r)/2;
active(id*2+1,l,m,x,y);
active(id*2+2,m+1,r,x,y);
act_c[id]=act_c[id*2+1]+act_c[id*2+2];
}
void update(int id,int l,int r,int p,int v) {
if(l==r) {
act_c[id]+=v;
return;
}
int m=(l+r)/2;
if(p<=m) update(id*2+1,l,m,p,v);
else update(id*2+2,m+1,r,p,v);
act_c[id]=act_c[id*2+1]+act_c[id*2+2];
}
stack<int> s[2];
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d %d",&a[i],&b[i]);
for(int i=1;i<=n;i++) {
ord[a[i]]=i;
ord[b[i]]=-i;
par[i]=i;
tq[i]=new treap(b[i],rng());
}
//cerr<<"ok1"<<endl;
for(int i=1;i<=2*n;i++) {
//cerr<<i<<" "<<ord[i]<<endl;
if(ord[i]>0) {
int j=ord[i];
cur_c.clear();
active(0,1,2*n,a[j],b[j]);
for(auto comp:cur_c) {
int u=find_par(comp);
int v=find_par(j);
if(u!=v) {
c[j].push_back(comp);
c[comp].push_back(j);
//cerr<<"iu"<<endl;
unite(u,v);
//cerr<<"ou"<<endl;
}
}
int u=find_par(j);
//cerr<<"ook2."<<i<<endl;
//assert(tq[u]!=NULL);
//cerr<<left(tq[u])<<endl;
update(0,1,2*n,left(tq[u]),1);
}
else {
int j=-ord[i];
//print_par();
int u=find_par(j);
//cerr<<j<<" "<<u<<" "<<pq[u].size()<<endl;
update(0,1,2*n,left(tq[u]),-1);
pop_left(tq[u]);
if(tq[u]!=NULL) update(0,1,2*n,left(tq[u]),1);
}
//cerr<<"ok2."<<i<<endl;
}
//cerr<<"ok2"<<endl;
//print_par();
long long ans=1;
for(int i=1;i<=n;i++) {
if(!vis[i]) {
dfs(i);
ans=(ans*2)%mod;
}
}
for(int i=1;i<=2*n;i++) {
if(ord[i]>0) {
int j=ord[i];
s[d[j]].push(j);
}
else {
int j=-ord[i];
if(s[d[j]].top()!=j) {
printf("0");
return 0;
}
s[d[j]].pop();
}
}
printf("%lld",ans);
return 0;
}
Compilation message (stderr)
port_facility.cpp: In function 'int main()':
port_facility.cpp:145:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
145 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
port_facility.cpp:146:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
146 | for(int i=1;i<=n;i++) scanf("%d %d",&a[i],&b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# | 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... |