#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;
priority_queue<int> pq[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(pq[u].size()>pq[v].size()) swap(u,v);
par[u]=v;
while(!pq[u].empty()) {
pq[v].push(pq[u].top());
pq[u].pop();
}
}
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;
pq[i].push(-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,-pq[u].top(),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,-pq[u].top(),-1);
pq[u].pop();
if(!pq[u].empty()) update(0,1,2*n,-pq[u].top(),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:77:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
77 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
port_facility.cpp:78:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
78 | for(int i=1;i<=n;i++) scanf("%d %d",&a[i],&b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
137324 KB |
Output is correct |
2 |
Correct |
82 ms |
137324 KB |
Output is correct |
3 |
Correct |
82 ms |
137324 KB |
Output is correct |
4 |
Correct |
83 ms |
137324 KB |
Output is correct |
5 |
Correct |
84 ms |
137464 KB |
Output is correct |
6 |
Correct |
82 ms |
137472 KB |
Output is correct |
7 |
Correct |
82 ms |
137324 KB |
Output is correct |
8 |
Correct |
82 ms |
137344 KB |
Output is correct |
9 |
Correct |
82 ms |
137452 KB |
Output is correct |
10 |
Correct |
82 ms |
137324 KB |
Output is correct |
11 |
Correct |
82 ms |
137324 KB |
Output is correct |
12 |
Correct |
85 ms |
137344 KB |
Output is correct |
13 |
Correct |
84 ms |
137344 KB |
Output is correct |
14 |
Correct |
84 ms |
137472 KB |
Output is correct |
15 |
Correct |
85 ms |
137452 KB |
Output is correct |
16 |
Correct |
85 ms |
137472 KB |
Output is correct |
17 |
Correct |
84 ms |
137452 KB |
Output is correct |
18 |
Correct |
83 ms |
137324 KB |
Output is correct |
19 |
Correct |
91 ms |
137452 KB |
Output is correct |
20 |
Correct |
85 ms |
137452 KB |
Output is correct |
21 |
Correct |
84 ms |
137328 KB |
Output is correct |
22 |
Correct |
84 ms |
137324 KB |
Output is correct |
23 |
Correct |
83 ms |
137336 KB |
Output is correct |
24 |
Correct |
83 ms |
137324 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
137324 KB |
Output is correct |
2 |
Correct |
82 ms |
137324 KB |
Output is correct |
3 |
Correct |
82 ms |
137324 KB |
Output is correct |
4 |
Correct |
83 ms |
137324 KB |
Output is correct |
5 |
Correct |
84 ms |
137464 KB |
Output is correct |
6 |
Correct |
82 ms |
137472 KB |
Output is correct |
7 |
Correct |
82 ms |
137324 KB |
Output is correct |
8 |
Correct |
82 ms |
137344 KB |
Output is correct |
9 |
Correct |
82 ms |
137452 KB |
Output is correct |
10 |
Correct |
82 ms |
137324 KB |
Output is correct |
11 |
Correct |
82 ms |
137324 KB |
Output is correct |
12 |
Correct |
85 ms |
137344 KB |
Output is correct |
13 |
Correct |
84 ms |
137344 KB |
Output is correct |
14 |
Correct |
84 ms |
137472 KB |
Output is correct |
15 |
Correct |
85 ms |
137452 KB |
Output is correct |
16 |
Correct |
85 ms |
137472 KB |
Output is correct |
17 |
Correct |
84 ms |
137452 KB |
Output is correct |
18 |
Correct |
83 ms |
137324 KB |
Output is correct |
19 |
Correct |
91 ms |
137452 KB |
Output is correct |
20 |
Correct |
85 ms |
137452 KB |
Output is correct |
21 |
Correct |
84 ms |
137328 KB |
Output is correct |
22 |
Correct |
84 ms |
137324 KB |
Output is correct |
23 |
Correct |
83 ms |
137336 KB |
Output is correct |
24 |
Correct |
83 ms |
137324 KB |
Output is correct |
25 |
Correct |
87 ms |
137652 KB |
Output is correct |
26 |
Correct |
93 ms |
137580 KB |
Output is correct |
27 |
Correct |
87 ms |
137580 KB |
Output is correct |
28 |
Correct |
87 ms |
137580 KB |
Output is correct |
29 |
Correct |
92 ms |
137708 KB |
Output is correct |
30 |
Correct |
86 ms |
137708 KB |
Output is correct |
31 |
Correct |
86 ms |
137580 KB |
Output is correct |
32 |
Correct |
90 ms |
137644 KB |
Output is correct |
33 |
Correct |
88 ms |
137580 KB |
Output is correct |
34 |
Correct |
86 ms |
137580 KB |
Output is correct |
35 |
Correct |
84 ms |
137452 KB |
Output is correct |
36 |
Correct |
86 ms |
137452 KB |
Output is correct |
37 |
Correct |
86 ms |
137580 KB |
Output is correct |
38 |
Correct |
86 ms |
137580 KB |
Output is correct |
39 |
Correct |
86 ms |
137580 KB |
Output is correct |
40 |
Correct |
86 ms |
137452 KB |
Output is correct |
41 |
Correct |
86 ms |
137580 KB |
Output is correct |
42 |
Correct |
88 ms |
137580 KB |
Output is correct |
43 |
Correct |
87 ms |
137580 KB |
Output is correct |
44 |
Correct |
85 ms |
137580 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
137324 KB |
Output is correct |
2 |
Correct |
82 ms |
137324 KB |
Output is correct |
3 |
Correct |
82 ms |
137324 KB |
Output is correct |
4 |
Correct |
83 ms |
137324 KB |
Output is correct |
5 |
Correct |
84 ms |
137464 KB |
Output is correct |
6 |
Correct |
82 ms |
137472 KB |
Output is correct |
7 |
Correct |
82 ms |
137324 KB |
Output is correct |
8 |
Correct |
82 ms |
137344 KB |
Output is correct |
9 |
Correct |
82 ms |
137452 KB |
Output is correct |
10 |
Correct |
82 ms |
137324 KB |
Output is correct |
11 |
Correct |
82 ms |
137324 KB |
Output is correct |
12 |
Correct |
85 ms |
137344 KB |
Output is correct |
13 |
Correct |
84 ms |
137344 KB |
Output is correct |
14 |
Correct |
84 ms |
137472 KB |
Output is correct |
15 |
Correct |
85 ms |
137452 KB |
Output is correct |
16 |
Correct |
85 ms |
137472 KB |
Output is correct |
17 |
Correct |
84 ms |
137452 KB |
Output is correct |
18 |
Correct |
83 ms |
137324 KB |
Output is correct |
19 |
Correct |
91 ms |
137452 KB |
Output is correct |
20 |
Correct |
85 ms |
137452 KB |
Output is correct |
21 |
Correct |
84 ms |
137328 KB |
Output is correct |
22 |
Correct |
84 ms |
137324 KB |
Output is correct |
23 |
Correct |
83 ms |
137336 KB |
Output is correct |
24 |
Correct |
83 ms |
137324 KB |
Output is correct |
25 |
Correct |
87 ms |
137652 KB |
Output is correct |
26 |
Correct |
93 ms |
137580 KB |
Output is correct |
27 |
Correct |
87 ms |
137580 KB |
Output is correct |
28 |
Correct |
87 ms |
137580 KB |
Output is correct |
29 |
Correct |
92 ms |
137708 KB |
Output is correct |
30 |
Correct |
86 ms |
137708 KB |
Output is correct |
31 |
Correct |
86 ms |
137580 KB |
Output is correct |
32 |
Correct |
90 ms |
137644 KB |
Output is correct |
33 |
Correct |
88 ms |
137580 KB |
Output is correct |
34 |
Correct |
86 ms |
137580 KB |
Output is correct |
35 |
Correct |
84 ms |
137452 KB |
Output is correct |
36 |
Correct |
86 ms |
137452 KB |
Output is correct |
37 |
Correct |
86 ms |
137580 KB |
Output is correct |
38 |
Correct |
86 ms |
137580 KB |
Output is correct |
39 |
Correct |
86 ms |
137580 KB |
Output is correct |
40 |
Correct |
86 ms |
137452 KB |
Output is correct |
41 |
Correct |
86 ms |
137580 KB |
Output is correct |
42 |
Correct |
88 ms |
137580 KB |
Output is correct |
43 |
Correct |
87 ms |
137580 KB |
Output is correct |
44 |
Correct |
85 ms |
137580 KB |
Output is correct |
45 |
Correct |
283 ms |
149516 KB |
Output is correct |
46 |
Correct |
289 ms |
149740 KB |
Output is correct |
47 |
Correct |
287 ms |
149484 KB |
Output is correct |
48 |
Correct |
290 ms |
149996 KB |
Output is correct |
49 |
Correct |
287 ms |
149484 KB |
Output is correct |
50 |
Correct |
289 ms |
149740 KB |
Output is correct |
51 |
Correct |
283 ms |
149868 KB |
Output is correct |
52 |
Correct |
212 ms |
145828 KB |
Output is correct |
53 |
Correct |
253 ms |
145772 KB |
Output is correct |
54 |
Correct |
279 ms |
150108 KB |
Output is correct |
55 |
Correct |
283 ms |
149860 KB |
Output is correct |
56 |
Correct |
283 ms |
150000 KB |
Output is correct |
57 |
Correct |
262 ms |
149356 KB |
Output is correct |
58 |
Correct |
211 ms |
145900 KB |
Output is correct |
59 |
Correct |
235 ms |
146924 KB |
Output is correct |
60 |
Correct |
267 ms |
148460 KB |
Output is correct |
61 |
Correct |
281 ms |
149248 KB |
Output is correct |
62 |
Correct |
249 ms |
147948 KB |
Output is correct |
63 |
Correct |
265 ms |
148588 KB |
Output is correct |
64 |
Correct |
279 ms |
149120 KB |
Output is correct |
65 |
Correct |
309 ms |
149876 KB |
Output is correct |
66 |
Correct |
318 ms |
149864 KB |
Output is correct |
67 |
Correct |
290 ms |
149988 KB |
Output is correct |
68 |
Correct |
317 ms |
150116 KB |
Output is correct |
69 |
Correct |
292 ms |
150368 KB |
Output is correct |
70 |
Correct |
293 ms |
150240 KB |
Output is correct |
71 |
Correct |
281 ms |
150240 KB |
Output is correct |
72 |
Correct |
288 ms |
150368 KB |
Output is correct |
73 |
Correct |
286 ms |
150260 KB |
Output is correct |
74 |
Correct |
285 ms |
150240 KB |
Output is correct |
75 |
Correct |
266 ms |
152428 KB |
Output is correct |
76 |
Correct |
263 ms |
151916 KB |
Output is correct |
77 |
Correct |
266 ms |
153236 KB |
Output is correct |
78 |
Correct |
283 ms |
149740 KB |
Output is correct |
79 |
Correct |
291 ms |
149612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
82 ms |
137324 KB |
Output is correct |
2 |
Correct |
82 ms |
137324 KB |
Output is correct |
3 |
Correct |
82 ms |
137324 KB |
Output is correct |
4 |
Correct |
83 ms |
137324 KB |
Output is correct |
5 |
Correct |
84 ms |
137464 KB |
Output is correct |
6 |
Correct |
82 ms |
137472 KB |
Output is correct |
7 |
Correct |
82 ms |
137324 KB |
Output is correct |
8 |
Correct |
82 ms |
137344 KB |
Output is correct |
9 |
Correct |
82 ms |
137452 KB |
Output is correct |
10 |
Correct |
82 ms |
137324 KB |
Output is correct |
11 |
Correct |
82 ms |
137324 KB |
Output is correct |
12 |
Correct |
85 ms |
137344 KB |
Output is correct |
13 |
Correct |
84 ms |
137344 KB |
Output is correct |
14 |
Correct |
84 ms |
137472 KB |
Output is correct |
15 |
Correct |
85 ms |
137452 KB |
Output is correct |
16 |
Correct |
85 ms |
137472 KB |
Output is correct |
17 |
Correct |
84 ms |
137452 KB |
Output is correct |
18 |
Correct |
83 ms |
137324 KB |
Output is correct |
19 |
Correct |
91 ms |
137452 KB |
Output is correct |
20 |
Correct |
85 ms |
137452 KB |
Output is correct |
21 |
Correct |
84 ms |
137328 KB |
Output is correct |
22 |
Correct |
84 ms |
137324 KB |
Output is correct |
23 |
Correct |
83 ms |
137336 KB |
Output is correct |
24 |
Correct |
83 ms |
137324 KB |
Output is correct |
25 |
Correct |
87 ms |
137652 KB |
Output is correct |
26 |
Correct |
93 ms |
137580 KB |
Output is correct |
27 |
Correct |
87 ms |
137580 KB |
Output is correct |
28 |
Correct |
87 ms |
137580 KB |
Output is correct |
29 |
Correct |
92 ms |
137708 KB |
Output is correct |
30 |
Correct |
86 ms |
137708 KB |
Output is correct |
31 |
Correct |
86 ms |
137580 KB |
Output is correct |
32 |
Correct |
90 ms |
137644 KB |
Output is correct |
33 |
Correct |
88 ms |
137580 KB |
Output is correct |
34 |
Correct |
86 ms |
137580 KB |
Output is correct |
35 |
Correct |
84 ms |
137452 KB |
Output is correct |
36 |
Correct |
86 ms |
137452 KB |
Output is correct |
37 |
Correct |
86 ms |
137580 KB |
Output is correct |
38 |
Correct |
86 ms |
137580 KB |
Output is correct |
39 |
Correct |
86 ms |
137580 KB |
Output is correct |
40 |
Correct |
86 ms |
137452 KB |
Output is correct |
41 |
Correct |
86 ms |
137580 KB |
Output is correct |
42 |
Correct |
88 ms |
137580 KB |
Output is correct |
43 |
Correct |
87 ms |
137580 KB |
Output is correct |
44 |
Correct |
85 ms |
137580 KB |
Output is correct |
45 |
Correct |
283 ms |
149516 KB |
Output is correct |
46 |
Correct |
289 ms |
149740 KB |
Output is correct |
47 |
Correct |
287 ms |
149484 KB |
Output is correct |
48 |
Correct |
290 ms |
149996 KB |
Output is correct |
49 |
Correct |
287 ms |
149484 KB |
Output is correct |
50 |
Correct |
289 ms |
149740 KB |
Output is correct |
51 |
Correct |
283 ms |
149868 KB |
Output is correct |
52 |
Correct |
212 ms |
145828 KB |
Output is correct |
53 |
Correct |
253 ms |
145772 KB |
Output is correct |
54 |
Correct |
279 ms |
150108 KB |
Output is correct |
55 |
Correct |
283 ms |
149860 KB |
Output is correct |
56 |
Correct |
283 ms |
150000 KB |
Output is correct |
57 |
Correct |
262 ms |
149356 KB |
Output is correct |
58 |
Correct |
211 ms |
145900 KB |
Output is correct |
59 |
Correct |
235 ms |
146924 KB |
Output is correct |
60 |
Correct |
267 ms |
148460 KB |
Output is correct |
61 |
Correct |
281 ms |
149248 KB |
Output is correct |
62 |
Correct |
249 ms |
147948 KB |
Output is correct |
63 |
Correct |
265 ms |
148588 KB |
Output is correct |
64 |
Correct |
279 ms |
149120 KB |
Output is correct |
65 |
Correct |
309 ms |
149876 KB |
Output is correct |
66 |
Correct |
318 ms |
149864 KB |
Output is correct |
67 |
Correct |
290 ms |
149988 KB |
Output is correct |
68 |
Correct |
317 ms |
150116 KB |
Output is correct |
69 |
Correct |
292 ms |
150368 KB |
Output is correct |
70 |
Correct |
293 ms |
150240 KB |
Output is correct |
71 |
Correct |
281 ms |
150240 KB |
Output is correct |
72 |
Correct |
288 ms |
150368 KB |
Output is correct |
73 |
Correct |
286 ms |
150260 KB |
Output is correct |
74 |
Correct |
285 ms |
150240 KB |
Output is correct |
75 |
Correct |
266 ms |
152428 KB |
Output is correct |
76 |
Correct |
263 ms |
151916 KB |
Output is correct |
77 |
Correct |
266 ms |
153236 KB |
Output is correct |
78 |
Correct |
283 ms |
149740 KB |
Output is correct |
79 |
Correct |
291 ms |
149612 KB |
Output is correct |
80 |
Correct |
2731 ms |
255992 KB |
Output is correct |
81 |
Correct |
2720 ms |
255904 KB |
Output is correct |
82 |
Correct |
2706 ms |
255496 KB |
Output is correct |
83 |
Correct |
2729 ms |
255976 KB |
Output is correct |
84 |
Correct |
2700 ms |
256488 KB |
Output is correct |
85 |
Correct |
2692 ms |
255492 KB |
Output is correct |
86 |
Correct |
2787 ms |
255844 KB |
Output is correct |
87 |
Correct |
1739 ms |
220268 KB |
Output is correct |
88 |
Correct |
2324 ms |
220308 KB |
Output is correct |
89 |
Correct |
2722 ms |
263416 KB |
Output is correct |
90 |
Correct |
2704 ms |
261620 KB |
Output is correct |
91 |
Correct |
2681 ms |
261452 KB |
Output is correct |
92 |
Correct |
2334 ms |
255424 KB |
Output is correct |
93 |
Correct |
1774 ms |
220396 KB |
Output is correct |
94 |
Correct |
2220 ms |
237196 KB |
Output is correct |
95 |
Correct |
2543 ms |
251036 KB |
Output is correct |
96 |
Correct |
2629 ms |
254212 KB |
Output is correct |
97 |
Correct |
2256 ms |
241672 KB |
Output is correct |
98 |
Correct |
2512 ms |
251420 KB |
Output is correct |
99 |
Correct |
2562 ms |
254332 KB |
Output is correct |
100 |
Correct |
3311 ms |
260160 KB |
Output is correct |
101 |
Correct |
3327 ms |
260180 KB |
Output is correct |
102 |
Correct |
2890 ms |
262160 KB |
Output is correct |
103 |
Correct |
2898 ms |
262240 KB |
Output is correct |
104 |
Correct |
2879 ms |
263888 KB |
Output is correct |
105 |
Correct |
2831 ms |
263764 KB |
Output is correct |
106 |
Correct |
2904 ms |
265496 KB |
Output is correct |
107 |
Correct |
2859 ms |
265472 KB |
Output is correct |
108 |
Correct |
2893 ms |
264668 KB |
Output is correct |
109 |
Correct |
2823 ms |
264924 KB |
Output is correct |
110 |
Correct |
2567 ms |
301548 KB |
Output is correct |
111 |
Correct |
2400 ms |
298824 KB |
Output is correct |
112 |
Correct |
2395 ms |
290668 KB |
Output is correct |
113 |
Correct |
2711 ms |
255468 KB |
Output is correct |
114 |
Correct |
2730 ms |
255900 KB |
Output is correct |