#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
/* sorry, this is the bare minimum :'( */
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
// using vi = deque<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v).size()
#define fi first
#define se second
const int N = 1 << 21 | 2;
vi ls[N << 1];
int nn = 1, n;
int le[N];
int ptr[N << 1];
int A[N], B[N];
int par[N], dis[N];
int find(int u) {
if(par[u] == u) return u;
int p = find(par[u]);
dis[u] ^= dis[par[u]];
return par[u] = p;
}
bool unite(int u, int v, int c) {
int pu = find(u), pv = find(v);
if(pu == pv) {
return (dis[u] ^ dis[v]) == c;
} else {
if((dis[u] ^ dis[v]) != c) dis[pu] = 1;
par[pu] = pv;
return true;
}
}
void add_edge(int u, int v, int c) {
if(!unite(u, v, c)) {
puts("0");
exit(0);
}
}
void prefix(int u, int k, int id) {
vi& v = ls[u];
int& p = ptr[u];
if(sz(v) and A[v[0]] < k) {
add_edge(id, v[0], 1);
while(p < sz(v) and A[v[p]] < k)
++p;
}
}
void doshit(int l, int r, int k, int id) { // (l, r), < k
for(l += nn, r += nn; l+1 < r; l >>= 1, r >>= 1) {
if(~l & 1) prefix(l ^ 1, k, id);
if(r & 1) prefix(r ^ 1, k, id);
}
}
int main(int argc, char const *argv[])
{
#ifdef LOCAL
freopen("in", "r", stdin);
#endif
scanf("%d", &n);
iota(par, par+n, 0);
while(nn < n*2) nn <<= 1;
for(int i = 0; i < n; ++i) {
scanf("%d %d", &A[i], &B[i]);
A[i]--, B[i]--;
ls[B[i] + nn].emplace_back(i);
}
for(int i = nn-1; i >= 1; --i) {
ls[i].resize(sz(ls[i<<1])+sz(ls[i<<1|1]));
merge(all(ls[i<<1]), all(ls[i<<1|1]), ls[i].begin(), [](int x, int y){ return A[x] < A[y]; });
}
for(int i = 0; i < n; ++i) {
doshit(A[i], B[i], A[i], i);
}
for(int i = nn-1; i >= 1; --i) {
for(int j = 1; j < ptr[i]; ++j) {
add_edge(ls[i][j-1], ls[i][j], 0);
}
}
const int md = 1e9 + 7;
int ans = 1;
for(int i = 0; i < n; ++i) {
if(find(i) == i) {
if((ans <<= 1) >= md)
ans -= md;
}
}
printf("%d\n", ans);
return 0;
}
Compilation message
port_facility.cpp: In function 'int main(int, const char**)':
port_facility.cpp:72:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
72 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
port_facility.cpp:76:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
76 | scanf("%d %d", &A[i], &B[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
98796 KB |
Output is correct |
2 |
Correct |
63 ms |
98796 KB |
Output is correct |
3 |
Correct |
63 ms |
98796 KB |
Output is correct |
4 |
Correct |
62 ms |
98944 KB |
Output is correct |
5 |
Correct |
62 ms |
98924 KB |
Output is correct |
6 |
Correct |
62 ms |
98924 KB |
Output is correct |
7 |
Correct |
62 ms |
98796 KB |
Output is correct |
8 |
Correct |
61 ms |
98796 KB |
Output is correct |
9 |
Correct |
62 ms |
98828 KB |
Output is correct |
10 |
Correct |
62 ms |
98796 KB |
Output is correct |
11 |
Correct |
61 ms |
98796 KB |
Output is correct |
12 |
Correct |
62 ms |
98796 KB |
Output is correct |
13 |
Correct |
61 ms |
98796 KB |
Output is correct |
14 |
Correct |
61 ms |
98796 KB |
Output is correct |
15 |
Correct |
63 ms |
98796 KB |
Output is correct |
16 |
Correct |
63 ms |
98796 KB |
Output is correct |
17 |
Correct |
62 ms |
98796 KB |
Output is correct |
18 |
Correct |
63 ms |
98796 KB |
Output is correct |
19 |
Correct |
62 ms |
98796 KB |
Output is correct |
20 |
Correct |
62 ms |
98908 KB |
Output is correct |
21 |
Correct |
62 ms |
98796 KB |
Output is correct |
22 |
Correct |
62 ms |
98924 KB |
Output is correct |
23 |
Correct |
62 ms |
98816 KB |
Output is correct |
24 |
Correct |
62 ms |
98924 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
98796 KB |
Output is correct |
2 |
Correct |
63 ms |
98796 KB |
Output is correct |
3 |
Correct |
63 ms |
98796 KB |
Output is correct |
4 |
Correct |
62 ms |
98944 KB |
Output is correct |
5 |
Correct |
62 ms |
98924 KB |
Output is correct |
6 |
Correct |
62 ms |
98924 KB |
Output is correct |
7 |
Correct |
62 ms |
98796 KB |
Output is correct |
8 |
Correct |
61 ms |
98796 KB |
Output is correct |
9 |
Correct |
62 ms |
98828 KB |
Output is correct |
10 |
Correct |
62 ms |
98796 KB |
Output is correct |
11 |
Correct |
61 ms |
98796 KB |
Output is correct |
12 |
Correct |
62 ms |
98796 KB |
Output is correct |
13 |
Correct |
61 ms |
98796 KB |
Output is correct |
14 |
Correct |
61 ms |
98796 KB |
Output is correct |
15 |
Correct |
63 ms |
98796 KB |
Output is correct |
16 |
Correct |
63 ms |
98796 KB |
Output is correct |
17 |
Correct |
62 ms |
98796 KB |
Output is correct |
18 |
Correct |
63 ms |
98796 KB |
Output is correct |
19 |
Correct |
62 ms |
98796 KB |
Output is correct |
20 |
Correct |
62 ms |
98908 KB |
Output is correct |
21 |
Correct |
62 ms |
98796 KB |
Output is correct |
22 |
Correct |
62 ms |
98924 KB |
Output is correct |
23 |
Correct |
62 ms |
98816 KB |
Output is correct |
24 |
Correct |
62 ms |
98924 KB |
Output is correct |
25 |
Correct |
66 ms |
99180 KB |
Output is correct |
26 |
Correct |
63 ms |
99180 KB |
Output is correct |
27 |
Correct |
64 ms |
99180 KB |
Output is correct |
28 |
Correct |
63 ms |
99180 KB |
Output is correct |
29 |
Correct |
62 ms |
99104 KB |
Output is correct |
30 |
Correct |
64 ms |
99180 KB |
Output is correct |
31 |
Correct |
63 ms |
99180 KB |
Output is correct |
32 |
Correct |
63 ms |
99180 KB |
Output is correct |
33 |
Correct |
63 ms |
99180 KB |
Output is correct |
34 |
Correct |
62 ms |
99308 KB |
Output is correct |
35 |
Correct |
63 ms |
99180 KB |
Output is correct |
36 |
Correct |
64 ms |
99052 KB |
Output is correct |
37 |
Correct |
64 ms |
99052 KB |
Output is correct |
38 |
Correct |
63 ms |
99052 KB |
Output is correct |
39 |
Correct |
63 ms |
99180 KB |
Output is correct |
40 |
Correct |
64 ms |
99052 KB |
Output is correct |
41 |
Correct |
63 ms |
99180 KB |
Output is correct |
42 |
Correct |
64 ms |
99052 KB |
Output is correct |
43 |
Correct |
64 ms |
99180 KB |
Output is correct |
44 |
Correct |
65 ms |
99308 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
98796 KB |
Output is correct |
2 |
Correct |
63 ms |
98796 KB |
Output is correct |
3 |
Correct |
63 ms |
98796 KB |
Output is correct |
4 |
Correct |
62 ms |
98944 KB |
Output is correct |
5 |
Correct |
62 ms |
98924 KB |
Output is correct |
6 |
Correct |
62 ms |
98924 KB |
Output is correct |
7 |
Correct |
62 ms |
98796 KB |
Output is correct |
8 |
Correct |
61 ms |
98796 KB |
Output is correct |
9 |
Correct |
62 ms |
98828 KB |
Output is correct |
10 |
Correct |
62 ms |
98796 KB |
Output is correct |
11 |
Correct |
61 ms |
98796 KB |
Output is correct |
12 |
Correct |
62 ms |
98796 KB |
Output is correct |
13 |
Correct |
61 ms |
98796 KB |
Output is correct |
14 |
Correct |
61 ms |
98796 KB |
Output is correct |
15 |
Correct |
63 ms |
98796 KB |
Output is correct |
16 |
Correct |
63 ms |
98796 KB |
Output is correct |
17 |
Correct |
62 ms |
98796 KB |
Output is correct |
18 |
Correct |
63 ms |
98796 KB |
Output is correct |
19 |
Correct |
62 ms |
98796 KB |
Output is correct |
20 |
Correct |
62 ms |
98908 KB |
Output is correct |
21 |
Correct |
62 ms |
98796 KB |
Output is correct |
22 |
Correct |
62 ms |
98924 KB |
Output is correct |
23 |
Correct |
62 ms |
98816 KB |
Output is correct |
24 |
Correct |
62 ms |
98924 KB |
Output is correct |
25 |
Correct |
66 ms |
99180 KB |
Output is correct |
26 |
Correct |
63 ms |
99180 KB |
Output is correct |
27 |
Correct |
64 ms |
99180 KB |
Output is correct |
28 |
Correct |
63 ms |
99180 KB |
Output is correct |
29 |
Correct |
62 ms |
99104 KB |
Output is correct |
30 |
Correct |
64 ms |
99180 KB |
Output is correct |
31 |
Correct |
63 ms |
99180 KB |
Output is correct |
32 |
Correct |
63 ms |
99180 KB |
Output is correct |
33 |
Correct |
63 ms |
99180 KB |
Output is correct |
34 |
Correct |
62 ms |
99308 KB |
Output is correct |
35 |
Correct |
63 ms |
99180 KB |
Output is correct |
36 |
Correct |
64 ms |
99052 KB |
Output is correct |
37 |
Correct |
64 ms |
99052 KB |
Output is correct |
38 |
Correct |
63 ms |
99052 KB |
Output is correct |
39 |
Correct |
63 ms |
99180 KB |
Output is correct |
40 |
Correct |
64 ms |
99052 KB |
Output is correct |
41 |
Correct |
63 ms |
99180 KB |
Output is correct |
42 |
Correct |
64 ms |
99052 KB |
Output is correct |
43 |
Correct |
64 ms |
99180 KB |
Output is correct |
44 |
Correct |
65 ms |
99308 KB |
Output is correct |
45 |
Correct |
208 ms |
115564 KB |
Output is correct |
46 |
Correct |
218 ms |
115564 KB |
Output is correct |
47 |
Correct |
207 ms |
115436 KB |
Output is correct |
48 |
Correct |
210 ms |
115564 KB |
Output is correct |
49 |
Correct |
211 ms |
115436 KB |
Output is correct |
50 |
Correct |
139 ms |
115356 KB |
Output is correct |
51 |
Correct |
133 ms |
114668 KB |
Output is correct |
52 |
Correct |
133 ms |
114924 KB |
Output is correct |
53 |
Correct |
177 ms |
112236 KB |
Output is correct |
54 |
Correct |
119 ms |
113132 KB |
Output is correct |
55 |
Correct |
122 ms |
113132 KB |
Output is correct |
56 |
Correct |
126 ms |
113004 KB |
Output is correct |
57 |
Correct |
147 ms |
114540 KB |
Output is correct |
58 |
Correct |
136 ms |
113320 KB |
Output is correct |
59 |
Correct |
170 ms |
116076 KB |
Output is correct |
60 |
Correct |
179 ms |
115692 KB |
Output is correct |
61 |
Correct |
198 ms |
115712 KB |
Output is correct |
62 |
Correct |
135 ms |
114540 KB |
Output is correct |
63 |
Correct |
135 ms |
114412 KB |
Output is correct |
64 |
Correct |
141 ms |
115180 KB |
Output is correct |
65 |
Correct |
138 ms |
114028 KB |
Output is correct |
66 |
Correct |
140 ms |
114096 KB |
Output is correct |
67 |
Correct |
230 ms |
114412 KB |
Output is correct |
68 |
Correct |
231 ms |
114540 KB |
Output is correct |
69 |
Correct |
236 ms |
114412 KB |
Output is correct |
70 |
Correct |
234 ms |
114412 KB |
Output is correct |
71 |
Correct |
187 ms |
113132 KB |
Output is correct |
72 |
Correct |
190 ms |
113260 KB |
Output is correct |
73 |
Correct |
184 ms |
113132 KB |
Output is correct |
74 |
Correct |
184 ms |
113132 KB |
Output is correct |
75 |
Correct |
156 ms |
115692 KB |
Output is correct |
76 |
Correct |
161 ms |
116004 KB |
Output is correct |
77 |
Correct |
156 ms |
116076 KB |
Output is correct |
78 |
Correct |
215 ms |
115692 KB |
Output is correct |
79 |
Correct |
204 ms |
115540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
61 ms |
98796 KB |
Output is correct |
2 |
Correct |
63 ms |
98796 KB |
Output is correct |
3 |
Correct |
63 ms |
98796 KB |
Output is correct |
4 |
Correct |
62 ms |
98944 KB |
Output is correct |
5 |
Correct |
62 ms |
98924 KB |
Output is correct |
6 |
Correct |
62 ms |
98924 KB |
Output is correct |
7 |
Correct |
62 ms |
98796 KB |
Output is correct |
8 |
Correct |
61 ms |
98796 KB |
Output is correct |
9 |
Correct |
62 ms |
98828 KB |
Output is correct |
10 |
Correct |
62 ms |
98796 KB |
Output is correct |
11 |
Correct |
61 ms |
98796 KB |
Output is correct |
12 |
Correct |
62 ms |
98796 KB |
Output is correct |
13 |
Correct |
61 ms |
98796 KB |
Output is correct |
14 |
Correct |
61 ms |
98796 KB |
Output is correct |
15 |
Correct |
63 ms |
98796 KB |
Output is correct |
16 |
Correct |
63 ms |
98796 KB |
Output is correct |
17 |
Correct |
62 ms |
98796 KB |
Output is correct |
18 |
Correct |
63 ms |
98796 KB |
Output is correct |
19 |
Correct |
62 ms |
98796 KB |
Output is correct |
20 |
Correct |
62 ms |
98908 KB |
Output is correct |
21 |
Correct |
62 ms |
98796 KB |
Output is correct |
22 |
Correct |
62 ms |
98924 KB |
Output is correct |
23 |
Correct |
62 ms |
98816 KB |
Output is correct |
24 |
Correct |
62 ms |
98924 KB |
Output is correct |
25 |
Correct |
66 ms |
99180 KB |
Output is correct |
26 |
Correct |
63 ms |
99180 KB |
Output is correct |
27 |
Correct |
64 ms |
99180 KB |
Output is correct |
28 |
Correct |
63 ms |
99180 KB |
Output is correct |
29 |
Correct |
62 ms |
99104 KB |
Output is correct |
30 |
Correct |
64 ms |
99180 KB |
Output is correct |
31 |
Correct |
63 ms |
99180 KB |
Output is correct |
32 |
Correct |
63 ms |
99180 KB |
Output is correct |
33 |
Correct |
63 ms |
99180 KB |
Output is correct |
34 |
Correct |
62 ms |
99308 KB |
Output is correct |
35 |
Correct |
63 ms |
99180 KB |
Output is correct |
36 |
Correct |
64 ms |
99052 KB |
Output is correct |
37 |
Correct |
64 ms |
99052 KB |
Output is correct |
38 |
Correct |
63 ms |
99052 KB |
Output is correct |
39 |
Correct |
63 ms |
99180 KB |
Output is correct |
40 |
Correct |
64 ms |
99052 KB |
Output is correct |
41 |
Correct |
63 ms |
99180 KB |
Output is correct |
42 |
Correct |
64 ms |
99052 KB |
Output is correct |
43 |
Correct |
64 ms |
99180 KB |
Output is correct |
44 |
Correct |
65 ms |
99308 KB |
Output is correct |
45 |
Correct |
208 ms |
115564 KB |
Output is correct |
46 |
Correct |
218 ms |
115564 KB |
Output is correct |
47 |
Correct |
207 ms |
115436 KB |
Output is correct |
48 |
Correct |
210 ms |
115564 KB |
Output is correct |
49 |
Correct |
211 ms |
115436 KB |
Output is correct |
50 |
Correct |
139 ms |
115356 KB |
Output is correct |
51 |
Correct |
133 ms |
114668 KB |
Output is correct |
52 |
Correct |
133 ms |
114924 KB |
Output is correct |
53 |
Correct |
177 ms |
112236 KB |
Output is correct |
54 |
Correct |
119 ms |
113132 KB |
Output is correct |
55 |
Correct |
122 ms |
113132 KB |
Output is correct |
56 |
Correct |
126 ms |
113004 KB |
Output is correct |
57 |
Correct |
147 ms |
114540 KB |
Output is correct |
58 |
Correct |
136 ms |
113320 KB |
Output is correct |
59 |
Correct |
170 ms |
116076 KB |
Output is correct |
60 |
Correct |
179 ms |
115692 KB |
Output is correct |
61 |
Correct |
198 ms |
115712 KB |
Output is correct |
62 |
Correct |
135 ms |
114540 KB |
Output is correct |
63 |
Correct |
135 ms |
114412 KB |
Output is correct |
64 |
Correct |
141 ms |
115180 KB |
Output is correct |
65 |
Correct |
138 ms |
114028 KB |
Output is correct |
66 |
Correct |
140 ms |
114096 KB |
Output is correct |
67 |
Correct |
230 ms |
114412 KB |
Output is correct |
68 |
Correct |
231 ms |
114540 KB |
Output is correct |
69 |
Correct |
236 ms |
114412 KB |
Output is correct |
70 |
Correct |
234 ms |
114412 KB |
Output is correct |
71 |
Correct |
187 ms |
113132 KB |
Output is correct |
72 |
Correct |
190 ms |
113260 KB |
Output is correct |
73 |
Correct |
184 ms |
113132 KB |
Output is correct |
74 |
Correct |
184 ms |
113132 KB |
Output is correct |
75 |
Correct |
156 ms |
115692 KB |
Output is correct |
76 |
Correct |
161 ms |
116004 KB |
Output is correct |
77 |
Correct |
156 ms |
116076 KB |
Output is correct |
78 |
Correct |
215 ms |
115692 KB |
Output is correct |
79 |
Correct |
204 ms |
115540 KB |
Output is correct |
80 |
Correct |
2774 ms |
277012 KB |
Output is correct |
81 |
Correct |
2815 ms |
277204 KB |
Output is correct |
82 |
Correct |
2658 ms |
276856 KB |
Output is correct |
83 |
Correct |
2751 ms |
276804 KB |
Output is correct |
84 |
Correct |
2847 ms |
276972 KB |
Output is correct |
85 |
Correct |
1227 ms |
267628 KB |
Output is correct |
86 |
Correct |
1228 ms |
268268 KB |
Output is correct |
87 |
Correct |
1201 ms |
271468 KB |
Output is correct |
88 |
Correct |
2282 ms |
244060 KB |
Output is correct |
89 |
Correct |
1059 ms |
249652 KB |
Output is correct |
90 |
Correct |
1100 ms |
250604 KB |
Output is correct |
91 |
Correct |
1079 ms |
251244 KB |
Output is correct |
92 |
Correct |
1382 ms |
267372 KB |
Output is correct |
93 |
Correct |
1226 ms |
255724 KB |
Output is correct |
94 |
Correct |
1858 ms |
280556 KB |
Output is correct |
95 |
Correct |
2205 ms |
277740 KB |
Output is correct |
96 |
Correct |
2452 ms |
277324 KB |
Output is correct |
97 |
Correct |
1215 ms |
265324 KB |
Output is correct |
98 |
Correct |
1235 ms |
270196 KB |
Output is correct |
99 |
Correct |
1203 ms |
262508 KB |
Output is correct |
100 |
Correct |
1333 ms |
259180 KB |
Output is correct |
101 |
Correct |
1301 ms |
258412 KB |
Output is correct |
102 |
Correct |
3419 ms |
266348 KB |
Output is correct |
103 |
Correct |
3368 ms |
266220 KB |
Output is correct |
104 |
Correct |
3422 ms |
266544 KB |
Output is correct |
105 |
Correct |
3511 ms |
266588 KB |
Output is correct |
106 |
Correct |
2431 ms |
256436 KB |
Output is correct |
107 |
Correct |
2429 ms |
256108 KB |
Output is correct |
108 |
Correct |
2437 ms |
256260 KB |
Output is correct |
109 |
Correct |
2389 ms |
256020 KB |
Output is correct |
110 |
Correct |
1677 ms |
279052 KB |
Output is correct |
111 |
Correct |
1721 ms |
283116 KB |
Output is correct |
112 |
Correct |
1712 ms |
283164 KB |
Output is correct |
113 |
Correct |
2699 ms |
276972 KB |
Output is correct |
114 |
Correct |
2820 ms |
276928 KB |
Output is correct |