#include <bits/stdc++.h>
using namespace std;
#define Fi first
#define Se second
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;
int N, X[2000020], A[1000010], B[1000010];
vector <int> E[1000010];
int nxt[1000010], pre[1000010], tail[1000010];
int pp[1000010], vis[1000010]; int Find(int x) { return pp[x] == x ? x : pp[x] = Find(pp[x]); }
vector <pii> edge;
void dfs(int x, int c) {
vis[x] = c;
for(int e : E[x]) if(!vis[e]) dfs(e, 3 - c);
}
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++) X[A[i]] = -i, X[B[i]] = i, nxt[i] = pre[i] = tail[i] = i;
vector <pii> w;
for(int i=1;i<=N;i++) pp[i] = i;
for(int i=1;i<=2*N;i++) {
int v = X[i];
if(v < 0) w.pb({-v, 1});
else {
int a = Find(v), px = -1, cnt = 0;
while(szz(w) && w.back().Fi != a) {
int pa = w.back().Fi;
cnt += w.back().Se;
if(px != -1) {
pp[px] = pa;
int t1 = tail[pa], t2 = px;
if(B[t1] < B[t2]) {
puts("0"); return 0;
}
nxt[t1] = t2; pre[t2] = t1;
tail[pa] = tail[px];
}
px = pa;
w.pop_back();
}
if(w.back().Se > 1) {
int p = w.back().Fi;
tail[p] = pre[tail[p]];
--w.back().Se;
}
else w.pop_back();
if(px != -1) edge.pb({px, a}), w.pb({px, cnt});
}
}
for(auto &[x, y] : edge) x = Find(x), y = Find(y), E[x].pb(y), E[y].pb(x);
int ans = 1;
for(int i=1;i<=N;i++) if(pp[i] == i && !vis[i]) {
dfs(i, 1);
ans = ans * 2 % 1000000007;
}
for(int i=1;i<=N;i++) for(int e : E[i]) if(vis[i] == vis[e]) ans = 0;
printf("%d\n", ans);
return 0;
}
Compilation message
port_facility.cpp: In function 'int main()':
port_facility.cpp:61:12: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
for(auto &[x, y] : edge) x = Find(x), y = Find(y), E[x].pb(y), E[y].pb(x);
^
port_facility.cpp:27:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
port_facility.cpp:28:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=1;i<=N;i++) scanf("%d%d", A+i, B+i);
~~~~~^~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23808 KB |
Output is correct |
2 |
Correct |
20 ms |
23808 KB |
Output is correct |
3 |
Correct |
19 ms |
23808 KB |
Output is correct |
4 |
Correct |
18 ms |
23936 KB |
Output is correct |
5 |
Correct |
19 ms |
23808 KB |
Output is correct |
6 |
Correct |
18 ms |
23808 KB |
Output is correct |
7 |
Correct |
19 ms |
23936 KB |
Output is correct |
8 |
Correct |
18 ms |
23808 KB |
Output is correct |
9 |
Correct |
19 ms |
23808 KB |
Output is correct |
10 |
Correct |
19 ms |
23808 KB |
Output is correct |
11 |
Correct |
19 ms |
23840 KB |
Output is correct |
12 |
Correct |
21 ms |
23808 KB |
Output is correct |
13 |
Correct |
19 ms |
23936 KB |
Output is correct |
14 |
Correct |
19 ms |
23936 KB |
Output is correct |
15 |
Correct |
18 ms |
23936 KB |
Output is correct |
16 |
Correct |
18 ms |
23808 KB |
Output is correct |
17 |
Correct |
21 ms |
23808 KB |
Output is correct |
18 |
Correct |
18 ms |
23808 KB |
Output is correct |
19 |
Correct |
18 ms |
23808 KB |
Output is correct |
20 |
Correct |
21 ms |
23936 KB |
Output is correct |
21 |
Correct |
18 ms |
23808 KB |
Output is correct |
22 |
Correct |
18 ms |
23808 KB |
Output is correct |
23 |
Correct |
18 ms |
23808 KB |
Output is correct |
24 |
Correct |
19 ms |
23808 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23808 KB |
Output is correct |
2 |
Correct |
20 ms |
23808 KB |
Output is correct |
3 |
Correct |
19 ms |
23808 KB |
Output is correct |
4 |
Correct |
18 ms |
23936 KB |
Output is correct |
5 |
Correct |
19 ms |
23808 KB |
Output is correct |
6 |
Correct |
18 ms |
23808 KB |
Output is correct |
7 |
Correct |
19 ms |
23936 KB |
Output is correct |
8 |
Correct |
18 ms |
23808 KB |
Output is correct |
9 |
Correct |
19 ms |
23808 KB |
Output is correct |
10 |
Correct |
19 ms |
23808 KB |
Output is correct |
11 |
Correct |
19 ms |
23840 KB |
Output is correct |
12 |
Correct |
21 ms |
23808 KB |
Output is correct |
13 |
Correct |
19 ms |
23936 KB |
Output is correct |
14 |
Correct |
19 ms |
23936 KB |
Output is correct |
15 |
Correct |
18 ms |
23936 KB |
Output is correct |
16 |
Correct |
18 ms |
23808 KB |
Output is correct |
17 |
Correct |
21 ms |
23808 KB |
Output is correct |
18 |
Correct |
18 ms |
23808 KB |
Output is correct |
19 |
Correct |
18 ms |
23808 KB |
Output is correct |
20 |
Correct |
21 ms |
23936 KB |
Output is correct |
21 |
Correct |
18 ms |
23808 KB |
Output is correct |
22 |
Correct |
18 ms |
23808 KB |
Output is correct |
23 |
Correct |
18 ms |
23808 KB |
Output is correct |
24 |
Correct |
19 ms |
23808 KB |
Output is correct |
25 |
Correct |
19 ms |
23936 KB |
Output is correct |
26 |
Correct |
19 ms |
23936 KB |
Output is correct |
27 |
Correct |
19 ms |
24192 KB |
Output is correct |
28 |
Correct |
20 ms |
23936 KB |
Output is correct |
29 |
Correct |
20 ms |
24192 KB |
Output is correct |
30 |
Correct |
21 ms |
23936 KB |
Output is correct |
31 |
Correct |
22 ms |
24064 KB |
Output is correct |
32 |
Correct |
20 ms |
23936 KB |
Output is correct |
33 |
Correct |
22 ms |
23936 KB |
Output is correct |
34 |
Correct |
22 ms |
23936 KB |
Output is correct |
35 |
Correct |
19 ms |
23936 KB |
Output is correct |
36 |
Correct |
19 ms |
23936 KB |
Output is correct |
37 |
Correct |
19 ms |
23936 KB |
Output is correct |
38 |
Correct |
19 ms |
23936 KB |
Output is correct |
39 |
Correct |
19 ms |
24064 KB |
Output is correct |
40 |
Correct |
21 ms |
23936 KB |
Output is correct |
41 |
Correct |
21 ms |
24064 KB |
Output is correct |
42 |
Correct |
19 ms |
24064 KB |
Output is correct |
43 |
Correct |
21 ms |
24064 KB |
Output is correct |
44 |
Correct |
20 ms |
24192 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23808 KB |
Output is correct |
2 |
Correct |
20 ms |
23808 KB |
Output is correct |
3 |
Correct |
19 ms |
23808 KB |
Output is correct |
4 |
Correct |
18 ms |
23936 KB |
Output is correct |
5 |
Correct |
19 ms |
23808 KB |
Output is correct |
6 |
Correct |
18 ms |
23808 KB |
Output is correct |
7 |
Correct |
19 ms |
23936 KB |
Output is correct |
8 |
Correct |
18 ms |
23808 KB |
Output is correct |
9 |
Correct |
19 ms |
23808 KB |
Output is correct |
10 |
Correct |
19 ms |
23808 KB |
Output is correct |
11 |
Correct |
19 ms |
23840 KB |
Output is correct |
12 |
Correct |
21 ms |
23808 KB |
Output is correct |
13 |
Correct |
19 ms |
23936 KB |
Output is correct |
14 |
Correct |
19 ms |
23936 KB |
Output is correct |
15 |
Correct |
18 ms |
23936 KB |
Output is correct |
16 |
Correct |
18 ms |
23808 KB |
Output is correct |
17 |
Correct |
21 ms |
23808 KB |
Output is correct |
18 |
Correct |
18 ms |
23808 KB |
Output is correct |
19 |
Correct |
18 ms |
23808 KB |
Output is correct |
20 |
Correct |
21 ms |
23936 KB |
Output is correct |
21 |
Correct |
18 ms |
23808 KB |
Output is correct |
22 |
Correct |
18 ms |
23808 KB |
Output is correct |
23 |
Correct |
18 ms |
23808 KB |
Output is correct |
24 |
Correct |
19 ms |
23808 KB |
Output is correct |
25 |
Correct |
19 ms |
23936 KB |
Output is correct |
26 |
Correct |
19 ms |
23936 KB |
Output is correct |
27 |
Correct |
19 ms |
24192 KB |
Output is correct |
28 |
Correct |
20 ms |
23936 KB |
Output is correct |
29 |
Correct |
20 ms |
24192 KB |
Output is correct |
30 |
Correct |
21 ms |
23936 KB |
Output is correct |
31 |
Correct |
22 ms |
24064 KB |
Output is correct |
32 |
Correct |
20 ms |
23936 KB |
Output is correct |
33 |
Correct |
22 ms |
23936 KB |
Output is correct |
34 |
Correct |
22 ms |
23936 KB |
Output is correct |
35 |
Correct |
19 ms |
23936 KB |
Output is correct |
36 |
Correct |
19 ms |
23936 KB |
Output is correct |
37 |
Correct |
19 ms |
23936 KB |
Output is correct |
38 |
Correct |
19 ms |
23936 KB |
Output is correct |
39 |
Correct |
19 ms |
24064 KB |
Output is correct |
40 |
Correct |
21 ms |
23936 KB |
Output is correct |
41 |
Correct |
21 ms |
24064 KB |
Output is correct |
42 |
Correct |
19 ms |
24064 KB |
Output is correct |
43 |
Correct |
21 ms |
24064 KB |
Output is correct |
44 |
Correct |
20 ms |
24192 KB |
Output is correct |
45 |
Correct |
74 ms |
30960 KB |
Output is correct |
46 |
Correct |
66 ms |
30832 KB |
Output is correct |
47 |
Correct |
104 ms |
30960 KB |
Output is correct |
48 |
Correct |
67 ms |
30832 KB |
Output is correct |
49 |
Correct |
66 ms |
30960 KB |
Output is correct |
50 |
Correct |
55 ms |
29424 KB |
Output is correct |
51 |
Correct |
54 ms |
28892 KB |
Output is correct |
52 |
Correct |
51 ms |
28664 KB |
Output is correct |
53 |
Correct |
54 ms |
29548 KB |
Output is correct |
54 |
Correct |
49 ms |
29552 KB |
Output is correct |
55 |
Correct |
50 ms |
28916 KB |
Output is correct |
56 |
Correct |
52 ms |
28916 KB |
Output is correct |
57 |
Correct |
69 ms |
32112 KB |
Output is correct |
58 |
Correct |
55 ms |
28664 KB |
Output is correct |
59 |
Correct |
57 ms |
29424 KB |
Output is correct |
60 |
Correct |
62 ms |
30580 KB |
Output is correct |
61 |
Correct |
66 ms |
30704 KB |
Output is correct |
62 |
Correct |
53 ms |
28916 KB |
Output is correct |
63 |
Correct |
49 ms |
28536 KB |
Output is correct |
64 |
Correct |
53 ms |
29172 KB |
Output is correct |
65 |
Correct |
50 ms |
28916 KB |
Output is correct |
66 |
Correct |
50 ms |
29044 KB |
Output is correct |
67 |
Correct |
65 ms |
31216 KB |
Output is correct |
68 |
Correct |
63 ms |
31216 KB |
Output is correct |
69 |
Correct |
61 ms |
30448 KB |
Output is correct |
70 |
Correct |
69 ms |
30412 KB |
Output is correct |
71 |
Correct |
64 ms |
32364 KB |
Output is correct |
72 |
Correct |
63 ms |
32364 KB |
Output is correct |
73 |
Correct |
61 ms |
31980 KB |
Output is correct |
74 |
Correct |
61 ms |
31980 KB |
Output is correct |
75 |
Correct |
74 ms |
35308 KB |
Output is correct |
76 |
Correct |
79 ms |
37228 KB |
Output is correct |
77 |
Correct |
77 ms |
37204 KB |
Output is correct |
78 |
Correct |
65 ms |
30832 KB |
Output is correct |
79 |
Correct |
73 ms |
30832 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
23808 KB |
Output is correct |
2 |
Correct |
20 ms |
23808 KB |
Output is correct |
3 |
Correct |
19 ms |
23808 KB |
Output is correct |
4 |
Correct |
18 ms |
23936 KB |
Output is correct |
5 |
Correct |
19 ms |
23808 KB |
Output is correct |
6 |
Correct |
18 ms |
23808 KB |
Output is correct |
7 |
Correct |
19 ms |
23936 KB |
Output is correct |
8 |
Correct |
18 ms |
23808 KB |
Output is correct |
9 |
Correct |
19 ms |
23808 KB |
Output is correct |
10 |
Correct |
19 ms |
23808 KB |
Output is correct |
11 |
Correct |
19 ms |
23840 KB |
Output is correct |
12 |
Correct |
21 ms |
23808 KB |
Output is correct |
13 |
Correct |
19 ms |
23936 KB |
Output is correct |
14 |
Correct |
19 ms |
23936 KB |
Output is correct |
15 |
Correct |
18 ms |
23936 KB |
Output is correct |
16 |
Correct |
18 ms |
23808 KB |
Output is correct |
17 |
Correct |
21 ms |
23808 KB |
Output is correct |
18 |
Correct |
18 ms |
23808 KB |
Output is correct |
19 |
Correct |
18 ms |
23808 KB |
Output is correct |
20 |
Correct |
21 ms |
23936 KB |
Output is correct |
21 |
Correct |
18 ms |
23808 KB |
Output is correct |
22 |
Correct |
18 ms |
23808 KB |
Output is correct |
23 |
Correct |
18 ms |
23808 KB |
Output is correct |
24 |
Correct |
19 ms |
23808 KB |
Output is correct |
25 |
Correct |
19 ms |
23936 KB |
Output is correct |
26 |
Correct |
19 ms |
23936 KB |
Output is correct |
27 |
Correct |
19 ms |
24192 KB |
Output is correct |
28 |
Correct |
20 ms |
23936 KB |
Output is correct |
29 |
Correct |
20 ms |
24192 KB |
Output is correct |
30 |
Correct |
21 ms |
23936 KB |
Output is correct |
31 |
Correct |
22 ms |
24064 KB |
Output is correct |
32 |
Correct |
20 ms |
23936 KB |
Output is correct |
33 |
Correct |
22 ms |
23936 KB |
Output is correct |
34 |
Correct |
22 ms |
23936 KB |
Output is correct |
35 |
Correct |
19 ms |
23936 KB |
Output is correct |
36 |
Correct |
19 ms |
23936 KB |
Output is correct |
37 |
Correct |
19 ms |
23936 KB |
Output is correct |
38 |
Correct |
19 ms |
23936 KB |
Output is correct |
39 |
Correct |
19 ms |
24064 KB |
Output is correct |
40 |
Correct |
21 ms |
23936 KB |
Output is correct |
41 |
Correct |
21 ms |
24064 KB |
Output is correct |
42 |
Correct |
19 ms |
24064 KB |
Output is correct |
43 |
Correct |
21 ms |
24064 KB |
Output is correct |
44 |
Correct |
20 ms |
24192 KB |
Output is correct |
45 |
Correct |
74 ms |
30960 KB |
Output is correct |
46 |
Correct |
66 ms |
30832 KB |
Output is correct |
47 |
Correct |
104 ms |
30960 KB |
Output is correct |
48 |
Correct |
67 ms |
30832 KB |
Output is correct |
49 |
Correct |
66 ms |
30960 KB |
Output is correct |
50 |
Correct |
55 ms |
29424 KB |
Output is correct |
51 |
Correct |
54 ms |
28892 KB |
Output is correct |
52 |
Correct |
51 ms |
28664 KB |
Output is correct |
53 |
Correct |
54 ms |
29548 KB |
Output is correct |
54 |
Correct |
49 ms |
29552 KB |
Output is correct |
55 |
Correct |
50 ms |
28916 KB |
Output is correct |
56 |
Correct |
52 ms |
28916 KB |
Output is correct |
57 |
Correct |
69 ms |
32112 KB |
Output is correct |
58 |
Correct |
55 ms |
28664 KB |
Output is correct |
59 |
Correct |
57 ms |
29424 KB |
Output is correct |
60 |
Correct |
62 ms |
30580 KB |
Output is correct |
61 |
Correct |
66 ms |
30704 KB |
Output is correct |
62 |
Correct |
53 ms |
28916 KB |
Output is correct |
63 |
Correct |
49 ms |
28536 KB |
Output is correct |
64 |
Correct |
53 ms |
29172 KB |
Output is correct |
65 |
Correct |
50 ms |
28916 KB |
Output is correct |
66 |
Correct |
50 ms |
29044 KB |
Output is correct |
67 |
Correct |
65 ms |
31216 KB |
Output is correct |
68 |
Correct |
63 ms |
31216 KB |
Output is correct |
69 |
Correct |
61 ms |
30448 KB |
Output is correct |
70 |
Correct |
69 ms |
30412 KB |
Output is correct |
71 |
Correct |
64 ms |
32364 KB |
Output is correct |
72 |
Correct |
63 ms |
32364 KB |
Output is correct |
73 |
Correct |
61 ms |
31980 KB |
Output is correct |
74 |
Correct |
61 ms |
31980 KB |
Output is correct |
75 |
Correct |
74 ms |
35308 KB |
Output is correct |
76 |
Correct |
79 ms |
37228 KB |
Output is correct |
77 |
Correct |
77 ms |
37204 KB |
Output is correct |
78 |
Correct |
65 ms |
30832 KB |
Output is correct |
79 |
Correct |
73 ms |
30832 KB |
Output is correct |
80 |
Correct |
862 ms |
95988 KB |
Output is correct |
81 |
Correct |
775 ms |
95912 KB |
Output is correct |
82 |
Correct |
739 ms |
96432 KB |
Output is correct |
83 |
Correct |
857 ms |
95972 KB |
Output is correct |
84 |
Correct |
757 ms |
95796 KB |
Output is correct |
85 |
Correct |
642 ms |
77004 KB |
Output is correct |
86 |
Correct |
385 ms |
73964 KB |
Output is correct |
87 |
Correct |
415 ms |
73528 KB |
Output is correct |
88 |
Correct |
378 ms |
81484 KB |
Output is correct |
89 |
Correct |
365 ms |
78028 KB |
Output is correct |
90 |
Correct |
365 ms |
73960 KB |
Output is correct |
91 |
Correct |
355 ms |
73960 KB |
Output is correct |
92 |
Correct |
803 ms |
108764 KB |
Output is correct |
93 |
Correct |
385 ms |
73720 KB |
Output is correct |
94 |
Correct |
611 ms |
88028 KB |
Output is correct |
95 |
Correct |
697 ms |
93132 KB |
Output is correct |
96 |
Correct |
762 ms |
94796 KB |
Output is correct |
97 |
Correct |
373 ms |
74852 KB |
Output is correct |
98 |
Correct |
395 ms |
73784 KB |
Output is correct |
99 |
Correct |
358 ms |
70752 KB |
Output is correct |
100 |
Correct |
374 ms |
73968 KB |
Output is correct |
101 |
Correct |
369 ms |
73832 KB |
Output is correct |
102 |
Correct |
738 ms |
99024 KB |
Output is correct |
103 |
Correct |
705 ms |
98988 KB |
Output is correct |
104 |
Correct |
675 ms |
90580 KB |
Output is correct |
105 |
Correct |
685 ms |
90580 KB |
Output is correct |
106 |
Correct |
766 ms |
110880 KB |
Output is correct |
107 |
Correct |
776 ms |
110796 KB |
Output is correct |
108 |
Correct |
758 ms |
106192 KB |
Output is correct |
109 |
Correct |
731 ms |
106316 KB |
Output is correct |
110 |
Correct |
1126 ms |
158676 KB |
Output is correct |
111 |
Correct |
1020 ms |
159616 KB |
Output is correct |
112 |
Correct |
1016 ms |
159924 KB |
Output is correct |
113 |
Correct |
753 ms |
96236 KB |
Output is correct |
114 |
Correct |
804 ms |
95824 KB |
Output is correct |