#include<bits/stdc++.h>
using namespace std;
#define maxn 1000005
#define mod 1000000007LL
#define inf 10000000
int n,bip;
int vis[maxn];
pair<int,int> p[maxn];
pair<int,int> tree[2][maxn*8];
void build(int now,int l,int r) {
if(l==r) {
tree[0][now] = tree[1][now] = {-inf,0};
return ;
}
int mid = (l+r)/2;
build(now<<1,l,mid); build(now<<1|1,mid+1,r);
tree[0][now] = tree[1][now] = {-inf,0};
}
void update(int num,int now,int l,int r,int x,pair<int,int> val) {
if(l>r || l>x || r<x) return ;
if(l==r) {
tree[num][now] = val;
return ;
}
int mid = (l+r)/2;
update(num,now<<1,l,mid,x,val); update(num,now<<1|1,mid+1,r,x,val);
tree[num][now] = max(tree[num][now<<1],tree[num][now<<1|1]);
}
pair<int,int> query(int num,int now,int l,int r,int x,int y) {
if(l>r || r<x || y<l) return {-inf,0};
if(x<=l && r<=y) return tree[num][now];
int mid = (l+r)/2;
return max(query(num,now<<1,l,mid,x,y),query(num,now<<1|1,mid+1,r,x,y));
}
void dfs(int x,int col) {
pair<int,int> t;
// printf("dfs %d : %d\n",x,col);
if(vis[x]==-1) vis[x] = col;
else {
update(0,1,1,2*n,p[x].first,{-inf,x});
update(1,1,1,2*n,p[x].second,{-inf,x});
if(vis[x]!=col) bip = 0;
}
while(1) {
t = query(0,1,1,2*n,p[x].first,p[x].second);
// printf("\tQ 0 [%d, %d] = {%d, %d}\n",p[x].first,p[x].second,t.first,t.second);
if(t.first<=p[x].second) break;
// printf("---- %d -> %d\n",x,t.second);
dfs(t.second,!col);
}
while(1) {
t = query(1,1,1,2*n,p[x].first,p[x].second);
// printf("\tQ 1 [%d, %d] = {%d, %d}\n",p[x].first,p[x].second,t.first,t.second);
if(-t.first>=p[x].first) break;
// printf("---- %d -> %d\n",x,t.second);
dfs(t.second,!col);
}
}
void checkbip() {
int i;
pair<int,int> t;
build(1,1,2*n);
for(i=1;i<=n;i++) update(vis[i],1,1,2*n,p[i].first,{p[i].second,i});
for(i=1;i<=n;i++) {
t = query(vis[i],1,1,2*n,p[i].first,p[i].second);
if(t.first>t.second) bip = 0;
}
}
long long pow(long long x,int y) {
if(y==0) return 1LL;
if(y%2!=0) return (pow(x,y-1)*x)%mod;
return pow((x*x)%mod,y/2);
}
main() {
int i,cnt;
scanf("%d",&n);
for(i=1;i<=n;i++) scanf("%d%d",&p[i].first,&p[i].second);
sort(&p[1],&p[n+1]);
build(1,1,2*n);
for(i=1;i<=n;i++) update(0,1,1,2*n,p[i].first,{p[i].second,i});
for(i=1;i<=n;i++) update(1,1,1,2*n,p[i].second,{-p[i].first,i});
bip = 1; cnt = 0;
memset(vis,-1,sizeof(vis));
for(i=1;i<=n;i++) if(vis[i]==-1) dfs(i,0), cnt++;
checkbip();
if(!bip) printf("0");
else printf("%lld",pow(2LL,cnt));
}
Compilation message
port_facility.cpp:74:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
main() {
^
port_facility.cpp: In function 'int main()':
port_facility.cpp:76:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
^
port_facility.cpp:77:61: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(i=1;i<=n;i++) scanf("%d%d",&p[i].first,&p[i].second);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
138744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
138744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
138744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
138744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
