#include<bits/stdc++.h>
#define maxn 2500000
using namespace std;
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;
set<int> st[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) {
if(st[u].size()>st[v].size()) swap(u,v);
par[u]=v;
st[v].insert(st[u].begin(),st[u].end());
}
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;
st[i].insert(b[i]);
}
//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);
unite(u,v);
}
}
int u=find_par(j);
update(0,1,2*n,(*st[u].begin()),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,(*st[u].begin()),-1);
st[u].erase(st[u].begin());
if(!st[u].empty()) update(0,1,2*n,(*st[u].begin()),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
port_facility.cpp: In function 'int main()':
port_facility.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
74 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
port_facility.cpp:75:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
75 | for(int i=1;i<=n;i++) scanf("%d %d",&a[i],&b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
113 ms |
176512 KB |
Output is correct |
2 |
Correct |
110 ms |
176500 KB |
Output is correct |
3 |
Correct |
110 ms |
176492 KB |
Output is correct |
4 |
Correct |
107 ms |
176492 KB |
Output is correct |
5 |
Correct |
109 ms |
176492 KB |
Output is correct |
6 |
Correct |
108 ms |
176492 KB |
Output is correct |
7 |
Correct |
109 ms |
176512 KB |
Output is correct |
8 |
Correct |
110 ms |
176492 KB |
Output is correct |
9 |
Correct |
107 ms |
176492 KB |
Output is correct |
10 |
Correct |
108 ms |
176492 KB |
Output is correct |
11 |
Correct |
111 ms |
176492 KB |
Output is correct |
12 |
Correct |
108 ms |
176572 KB |
Output is correct |
13 |
Correct |
109 ms |
176524 KB |
Output is correct |
14 |
Correct |
108 ms |
176512 KB |
Output is correct |
15 |
Correct |
108 ms |
176492 KB |
Output is correct |
16 |
Correct |
110 ms |
176492 KB |
Output is correct |
17 |
Correct |
108 ms |
176492 KB |
Output is correct |
18 |
Correct |
109 ms |
176620 KB |
Output is correct |
19 |
Correct |
108 ms |
176492 KB |
Output is correct |
20 |
Correct |
109 ms |
176492 KB |
Output is correct |
21 |
Correct |
108 ms |
176492 KB |
Output is correct |
22 |
Correct |
110 ms |
176492 KB |
Output is correct |
23 |
Correct |
107 ms |
176492 KB |
Output is correct |
24 |
Correct |
110 ms |
176492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
113 ms |
176512 KB |
Output is correct |
2 |
Correct |
110 ms |
176500 KB |
Output is correct |
3 |
Correct |
110 ms |
176492 KB |
Output is correct |
4 |
Correct |
107 ms |
176492 KB |
Output is correct |
5 |
Correct |
109 ms |
176492 KB |
Output is correct |
6 |
Correct |
108 ms |
176492 KB |
Output is correct |
7 |
Correct |
109 ms |
176512 KB |
Output is correct |
8 |
Correct |
110 ms |
176492 KB |
Output is correct |
9 |
Correct |
107 ms |
176492 KB |
Output is correct |
10 |
Correct |
108 ms |
176492 KB |
Output is correct |
11 |
Correct |
111 ms |
176492 KB |
Output is correct |
12 |
Correct |
108 ms |
176572 KB |
Output is correct |
13 |
Correct |
109 ms |
176524 KB |
Output is correct |
14 |
Correct |
108 ms |
176512 KB |
Output is correct |
15 |
Correct |
108 ms |
176492 KB |
Output is correct |
16 |
Correct |
110 ms |
176492 KB |
Output is correct |
17 |
Correct |
108 ms |
176492 KB |
Output is correct |
18 |
Correct |
109 ms |
176620 KB |
Output is correct |
19 |
Correct |
108 ms |
176492 KB |
Output is correct |
20 |
Correct |
109 ms |
176492 KB |
Output is correct |
21 |
Correct |
108 ms |
176492 KB |
Output is correct |
22 |
Correct |
110 ms |
176492 KB |
Output is correct |
23 |
Correct |
107 ms |
176492 KB |
Output is correct |
24 |
Correct |
110 ms |
176492 KB |
Output is correct |
25 |
Correct |
114 ms |
176804 KB |
Output is correct |
26 |
Correct |
121 ms |
176876 KB |
Output is correct |
27 |
Correct |
114 ms |
176876 KB |
Output is correct |
28 |
Correct |
112 ms |
176876 KB |
Output is correct |
29 |
Correct |
112 ms |
176876 KB |
Output is correct |
30 |
Correct |
111 ms |
176876 KB |
Output is correct |
31 |
Correct |
111 ms |
176888 KB |
Output is correct |
32 |
Correct |
113 ms |
176804 KB |
Output is correct |
33 |
Correct |
114 ms |
176876 KB |
Output is correct |
34 |
Correct |
112 ms |
176748 KB |
Output is correct |
35 |
Correct |
110 ms |
176748 KB |
Output is correct |
36 |
Correct |
111 ms |
176748 KB |
Output is correct |
37 |
Correct |
112 ms |
177004 KB |
Output is correct |
38 |
Correct |
112 ms |
176876 KB |
Output is correct |
39 |
Correct |
113 ms |
176748 KB |
Output is correct |
40 |
Correct |
110 ms |
176748 KB |
Output is correct |
41 |
Correct |
113 ms |
176876 KB |
Output is correct |
42 |
Correct |
119 ms |
176876 KB |
Output is correct |
43 |
Correct |
110 ms |
176876 KB |
Output is correct |
44 |
Correct |
111 ms |
176876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
113 ms |
176512 KB |
Output is correct |
2 |
Correct |
110 ms |
176500 KB |
Output is correct |
3 |
Correct |
110 ms |
176492 KB |
Output is correct |
4 |
Correct |
107 ms |
176492 KB |
Output is correct |
5 |
Correct |
109 ms |
176492 KB |
Output is correct |
6 |
Correct |
108 ms |
176492 KB |
Output is correct |
7 |
Correct |
109 ms |
176512 KB |
Output is correct |
8 |
Correct |
110 ms |
176492 KB |
Output is correct |
9 |
Correct |
107 ms |
176492 KB |
Output is correct |
10 |
Correct |
108 ms |
176492 KB |
Output is correct |
11 |
Correct |
111 ms |
176492 KB |
Output is correct |
12 |
Correct |
108 ms |
176572 KB |
Output is correct |
13 |
Correct |
109 ms |
176524 KB |
Output is correct |
14 |
Correct |
108 ms |
176512 KB |
Output is correct |
15 |
Correct |
108 ms |
176492 KB |
Output is correct |
16 |
Correct |
110 ms |
176492 KB |
Output is correct |
17 |
Correct |
108 ms |
176492 KB |
Output is correct |
18 |
Correct |
109 ms |
176620 KB |
Output is correct |
19 |
Correct |
108 ms |
176492 KB |
Output is correct |
20 |
Correct |
109 ms |
176492 KB |
Output is correct |
21 |
Correct |
108 ms |
176492 KB |
Output is correct |
22 |
Correct |
110 ms |
176492 KB |
Output is correct |
23 |
Correct |
107 ms |
176492 KB |
Output is correct |
24 |
Correct |
110 ms |
176492 KB |
Output is correct |
25 |
Correct |
114 ms |
176804 KB |
Output is correct |
26 |
Correct |
121 ms |
176876 KB |
Output is correct |
27 |
Correct |
114 ms |
176876 KB |
Output is correct |
28 |
Correct |
112 ms |
176876 KB |
Output is correct |
29 |
Correct |
112 ms |
176876 KB |
Output is correct |
30 |
Correct |
111 ms |
176876 KB |
Output is correct |
31 |
Correct |
111 ms |
176888 KB |
Output is correct |
32 |
Correct |
113 ms |
176804 KB |
Output is correct |
33 |
Correct |
114 ms |
176876 KB |
Output is correct |
34 |
Correct |
112 ms |
176748 KB |
Output is correct |
35 |
Correct |
110 ms |
176748 KB |
Output is correct |
36 |
Correct |
111 ms |
176748 KB |
Output is correct |
37 |
Correct |
112 ms |
177004 KB |
Output is correct |
38 |
Correct |
112 ms |
176876 KB |
Output is correct |
39 |
Correct |
113 ms |
176748 KB |
Output is correct |
40 |
Correct |
110 ms |
176748 KB |
Output is correct |
41 |
Correct |
113 ms |
176876 KB |
Output is correct |
42 |
Correct |
119 ms |
176876 KB |
Output is correct |
43 |
Correct |
110 ms |
176876 KB |
Output is correct |
44 |
Correct |
111 ms |
176876 KB |
Output is correct |
45 |
Correct |
339 ms |
192876 KB |
Output is correct |
46 |
Correct |
334 ms |
193148 KB |
Output is correct |
47 |
Correct |
337 ms |
192748 KB |
Output is correct |
48 |
Correct |
339 ms |
193260 KB |
Output is correct |
49 |
Correct |
339 ms |
192876 KB |
Output is correct |
50 |
Correct |
338 ms |
193004 KB |
Output is correct |
51 |
Correct |
334 ms |
193004 KB |
Output is correct |
52 |
Correct |
243 ms |
186732 KB |
Output is correct |
53 |
Correct |
285 ms |
186220 KB |
Output is correct |
54 |
Correct |
332 ms |
195044 KB |
Output is correct |
55 |
Correct |
328 ms |
193052 KB |
Output is correct |
56 |
Correct |
319 ms |
193000 KB |
Output is correct |
57 |
Correct |
285 ms |
188508 KB |
Output is correct |
58 |
Correct |
248 ms |
186604 KB |
Output is correct |
59 |
Correct |
278 ms |
187292 KB |
Output is correct |
60 |
Correct |
304 ms |
188396 KB |
Output is correct |
61 |
Correct |
321 ms |
190188 KB |
Output is correct |
62 |
Correct |
284 ms |
188580 KB |
Output is correct |
63 |
Correct |
309 ms |
189036 KB |
Output is correct |
64 |
Correct |
323 ms |
190316 KB |
Output is correct |
65 |
Correct |
404 ms |
192876 KB |
Output is correct |
66 |
Correct |
406 ms |
192688 KB |
Output is correct |
67 |
Correct |
343 ms |
193004 KB |
Output is correct |
68 |
Correct |
342 ms |
192876 KB |
Output is correct |
69 |
Correct |
339 ms |
193772 KB |
Output is correct |
70 |
Correct |
340 ms |
193784 KB |
Output is correct |
71 |
Correct |
343 ms |
195308 KB |
Output is correct |
72 |
Correct |
341 ms |
195564 KB |
Output is correct |
73 |
Correct |
341 ms |
195304 KB |
Output is correct |
74 |
Correct |
340 ms |
195304 KB |
Output is correct |
75 |
Correct |
291 ms |
193004 KB |
Output is correct |
76 |
Correct |
289 ms |
192620 KB |
Output is correct |
77 |
Correct |
290 ms |
193912 KB |
Output is correct |
78 |
Correct |
336 ms |
193132 KB |
Output is correct |
79 |
Correct |
333 ms |
192876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
113 ms |
176512 KB |
Output is correct |
2 |
Correct |
110 ms |
176500 KB |
Output is correct |
3 |
Correct |
110 ms |
176492 KB |
Output is correct |
4 |
Correct |
107 ms |
176492 KB |
Output is correct |
5 |
Correct |
109 ms |
176492 KB |
Output is correct |
6 |
Correct |
108 ms |
176492 KB |
Output is correct |
7 |
Correct |
109 ms |
176512 KB |
Output is correct |
8 |
Correct |
110 ms |
176492 KB |
Output is correct |
9 |
Correct |
107 ms |
176492 KB |
Output is correct |
10 |
Correct |
108 ms |
176492 KB |
Output is correct |
11 |
Correct |
111 ms |
176492 KB |
Output is correct |
12 |
Correct |
108 ms |
176572 KB |
Output is correct |
13 |
Correct |
109 ms |
176524 KB |
Output is correct |
14 |
Correct |
108 ms |
176512 KB |
Output is correct |
15 |
Correct |
108 ms |
176492 KB |
Output is correct |
16 |
Correct |
110 ms |
176492 KB |
Output is correct |
17 |
Correct |
108 ms |
176492 KB |
Output is correct |
18 |
Correct |
109 ms |
176620 KB |
Output is correct |
19 |
Correct |
108 ms |
176492 KB |
Output is correct |
20 |
Correct |
109 ms |
176492 KB |
Output is correct |
21 |
Correct |
108 ms |
176492 KB |
Output is correct |
22 |
Correct |
110 ms |
176492 KB |
Output is correct |
23 |
Correct |
107 ms |
176492 KB |
Output is correct |
24 |
Correct |
110 ms |
176492 KB |
Output is correct |
25 |
Correct |
114 ms |
176804 KB |
Output is correct |
26 |
Correct |
121 ms |
176876 KB |
Output is correct |
27 |
Correct |
114 ms |
176876 KB |
Output is correct |
28 |
Correct |
112 ms |
176876 KB |
Output is correct |
29 |
Correct |
112 ms |
176876 KB |
Output is correct |
30 |
Correct |
111 ms |
176876 KB |
Output is correct |
31 |
Correct |
111 ms |
176888 KB |
Output is correct |
32 |
Correct |
113 ms |
176804 KB |
Output is correct |
33 |
Correct |
114 ms |
176876 KB |
Output is correct |
34 |
Correct |
112 ms |
176748 KB |
Output is correct |
35 |
Correct |
110 ms |
176748 KB |
Output is correct |
36 |
Correct |
111 ms |
176748 KB |
Output is correct |
37 |
Correct |
112 ms |
177004 KB |
Output is correct |
38 |
Correct |
112 ms |
176876 KB |
Output is correct |
39 |
Correct |
113 ms |
176748 KB |
Output is correct |
40 |
Correct |
110 ms |
176748 KB |
Output is correct |
41 |
Correct |
113 ms |
176876 KB |
Output is correct |
42 |
Correct |
119 ms |
176876 KB |
Output is correct |
43 |
Correct |
110 ms |
176876 KB |
Output is correct |
44 |
Correct |
111 ms |
176876 KB |
Output is correct |
45 |
Correct |
339 ms |
192876 KB |
Output is correct |
46 |
Correct |
334 ms |
193148 KB |
Output is correct |
47 |
Correct |
337 ms |
192748 KB |
Output is correct |
48 |
Correct |
339 ms |
193260 KB |
Output is correct |
49 |
Correct |
339 ms |
192876 KB |
Output is correct |
50 |
Correct |
338 ms |
193004 KB |
Output is correct |
51 |
Correct |
334 ms |
193004 KB |
Output is correct |
52 |
Correct |
243 ms |
186732 KB |
Output is correct |
53 |
Correct |
285 ms |
186220 KB |
Output is correct |
54 |
Correct |
332 ms |
195044 KB |
Output is correct |
55 |
Correct |
328 ms |
193052 KB |
Output is correct |
56 |
Correct |
319 ms |
193000 KB |
Output is correct |
57 |
Correct |
285 ms |
188508 KB |
Output is correct |
58 |
Correct |
248 ms |
186604 KB |
Output is correct |
59 |
Correct |
278 ms |
187292 KB |
Output is correct |
60 |
Correct |
304 ms |
188396 KB |
Output is correct |
61 |
Correct |
321 ms |
190188 KB |
Output is correct |
62 |
Correct |
284 ms |
188580 KB |
Output is correct |
63 |
Correct |
309 ms |
189036 KB |
Output is correct |
64 |
Correct |
323 ms |
190316 KB |
Output is correct |
65 |
Correct |
404 ms |
192876 KB |
Output is correct |
66 |
Correct |
406 ms |
192688 KB |
Output is correct |
67 |
Correct |
343 ms |
193004 KB |
Output is correct |
68 |
Correct |
342 ms |
192876 KB |
Output is correct |
69 |
Correct |
339 ms |
193772 KB |
Output is correct |
70 |
Correct |
340 ms |
193784 KB |
Output is correct |
71 |
Correct |
343 ms |
195308 KB |
Output is correct |
72 |
Correct |
341 ms |
195564 KB |
Output is correct |
73 |
Correct |
341 ms |
195304 KB |
Output is correct |
74 |
Correct |
340 ms |
195304 KB |
Output is correct |
75 |
Correct |
291 ms |
193004 KB |
Output is correct |
76 |
Correct |
289 ms |
192620 KB |
Output is correct |
77 |
Correct |
290 ms |
193912 KB |
Output is correct |
78 |
Correct |
336 ms |
193132 KB |
Output is correct |
79 |
Correct |
333 ms |
192876 KB |
Output is correct |
80 |
Correct |
2966 ms |
329588 KB |
Output is correct |
81 |
Correct |
2969 ms |
328960 KB |
Output is correct |
82 |
Correct |
2935 ms |
327752 KB |
Output is correct |
83 |
Correct |
2959 ms |
328200 KB |
Output is correct |
84 |
Correct |
2995 ms |
329492 KB |
Output is correct |
85 |
Correct |
2911 ms |
326836 KB |
Output is correct |
86 |
Correct |
2942 ms |
328068 KB |
Output is correct |
87 |
Correct |
1913 ms |
267744 KB |
Output is correct |
88 |
Correct |
2519 ms |
263980 KB |
Output is correct |
89 |
Correct |
2898 ms |
354140 KB |
Output is correct |
90 |
Correct |
2815 ms |
328084 KB |
Output is correct |
91 |
Correct |
2886 ms |
329748 KB |
Output is correct |
92 |
Correct |
2378 ms |
284140 KB |
Output is correct |
93 |
Correct |
1941 ms |
265708 KB |
Output is correct |
94 |
Correct |
2504 ms |
271960 KB |
Output is correct |
95 |
Correct |
2788 ms |
297560 KB |
Output is correct |
96 |
Correct |
2853 ms |
309564 KB |
Output is correct |
97 |
Correct |
2486 ms |
282720 KB |
Output is correct |
98 |
Correct |
2738 ms |
298804 KB |
Output is correct |
99 |
Correct |
2840 ms |
306020 KB |
Output is correct |
100 |
Correct |
4583 ms |
326856 KB |
Output is correct |
101 |
Correct |
4654 ms |
324772 KB |
Output is correct |
102 |
Correct |
3153 ms |
326612 KB |
Output is correct |
103 |
Correct |
3190 ms |
326660 KB |
Output is correct |
104 |
Correct |
3122 ms |
337132 KB |
Output is correct |
105 |
Correct |
3132 ms |
335452 KB |
Output is correct |
106 |
Correct |
3153 ms |
352508 KB |
Output is correct |
107 |
Correct |
3139 ms |
353156 KB |
Output is correct |
108 |
Correct |
3144 ms |
352772 KB |
Output is correct |
109 |
Correct |
3141 ms |
352408 KB |
Output is correct |
110 |
Correct |
2483 ms |
345432 KB |
Output is correct |
111 |
Correct |
2501 ms |
340844 KB |
Output is correct |
112 |
Correct |
2481 ms |
332528 KB |
Output is correct |
113 |
Correct |
2917 ms |
322220 KB |
Output is correct |
114 |
Correct |
2954 ms |
326252 KB |
Output is correct |