#include <stdio.h>
#include <string.h>
#define N 1000000
#define N_ (1 << 21) /* N_ = pow2(ceil(log2(N * 2))) */
#define MD 1000000007
int ll[N], rr[N], n;
int stil[2][N_ * 2], stir[2][N_ * 2], n_;
void pul(int c, int i) {
int l = i << 1, r = l | 1, u, v;
u = stil[c][l], v = stil[c][r];
stil[c][i] = v == -1 || u != -1 && ll[u] < ll[v] ? u : v;
u = stir[c][l], v = stir[c][r];
stir[c][i] = v == -1 || u != -1 && rr[u] > rr[v] ? u : v;
}
void init() {
int c, i;
n_ = 1;
while (n_ < n * 2)
n_ <<= 1;
for (c = 0; c < 2; c++) {
memset(stil[c], -1, n_ * 2 * sizeof *stil[c]);
memset(stir[c], -1, n_ * 2 * sizeof *stir[c]);
for (i = 0; i < n; i++)
stil[c][n_ + rr[i]] = stir[c][n_ + ll[i]] = i;
for (i = n_ - 1; i > 0; i--)
pul(c, i);
}
}
int query_l(int c, int l, int r) {
int i_, i;
i_ = -1;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1) {
i = stil[c][l++];
if (i_ == -1 || i != -1 && ll[i_] > ll[i])
i_ = i;
}
if ((r & 1) == 0) {
i = stil[c][r--];
if (i_ == -1 || i != -1 && ll[i_] > ll[i])
i_ = i;
}
}
return i_;
}
int query_r(int c, int l, int r) {
int i_, i;
i_ = -1;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1) {
i = stir[c][l++];
if (i_ == -1 || i != -1 && rr[i_] < rr[i])
i_ = i;
}
if ((r & 1) == 0) {
i = stir[c][r--];
if (i_ == -1 || i != -1 && rr[i_] < rr[i])
i_ = i;
}
}
return i_;
}
void pull(int c, int i) {
while (i > 1)
pul(c, i >>= 1);
}
void remove_(int c, int i) {
stil[c][n_ + rr[i]] = -1, pull(c, n_ + rr[i]);
stir[c][n_ + ll[i]] = -1, pull(c, n_ + ll[i]);
}
int uu[2][N];
void dfs(int c, int i, int u) {
int j;
uu[c][i] = u;
remove_(c, i);
while ((j = query_l(c ^ 1, ll[i], rr[i])) != -1 && ll[j] < ll[i])
dfs(c ^ 1, j, u);
while ((j = query_r(c ^ 1, ll[i], rr[i])) != -1 && rr[j] > rr[i])
dfs(c ^ 1, j, u);
}
long long power(long long a, int k) {
long long p = 1;
while (k) {
if (k & 1)
p = p * a % MD;
a = a * a % MD;
k >>= 1;
}
return p;
}
int main() {
int c, i, k;
scanf("%d", &n);
for (i = 0; i < n; i++)
scanf("%d%d", &ll[i], &rr[i]), ll[i]--, rr[i]--;
init();
for (c = 0; c < 2; c++)
memset(uu[c], -1, n * sizeof *uu[c]);
k = 0;
for (c = 0; c < 2; c++)
for (i = 0; i < n; i++)
if (uu[c][i] == -1)
dfs(c, i, k++);
for (i = 0; i < n; i++)
if (uu[0][i] == uu[1][i]) {
printf("0\n");
return 0;
}
printf("%lld\n", power(2, k / 2));
return 0;
}
Compilation message
port_facility.c: In function 'pul':
port_facility.c:15:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
15 | stil[c][i] = v == -1 || u != -1 && ll[u] < ll[v] ? u : v;
| ~~~~~~~~^~~~~~~~~~~~~~~~
port_facility.c:17:34: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
17 | stir[c][i] = v == -1 || u != -1 && rr[u] > rr[v] ? u : v;
| ~~~~~~~~^~~~~~~~~~~~~~~~
port_facility.c: In function 'query_l':
port_facility.c:43:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
43 | if (i_ == -1 || i != -1 && ll[i_] > ll[i])
| ~~~~~~~~^~~~~~~~~~~~~~~~~
port_facility.c:48:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
48 | if (i_ == -1 || i != -1 && ll[i_] > ll[i])
| ~~~~~~~~^~~~~~~~~~~~~~~~~
port_facility.c: In function 'query_r':
port_facility.c:62:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
62 | if (i_ == -1 || i != -1 && rr[i_] < rr[i])
| ~~~~~~~~^~~~~~~~~~~~~~~~~
port_facility.c:67:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
67 | if (i_ == -1 || i != -1 && rr[i_] < rr[i])
| ~~~~~~~~^~~~~~~~~~~~~~~~~
port_facility.c: In function 'main':
port_facility.c:112:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
port_facility.c:114:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
114 | scanf("%d%d", &ll[i], &rr[i]), ll[i]--, rr[i]--;
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
292 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
292 KB |
Output is correct |
9 |
Correct |
0 ms |
288 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
296 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
292 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
292 KB |
Output is correct |
9 |
Correct |
0 ms |
288 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
296 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
3 ms |
468 KB |
Output is correct |
26 |
Correct |
4 ms |
596 KB |
Output is correct |
27 |
Correct |
3 ms |
468 KB |
Output is correct |
28 |
Correct |
3 ms |
596 KB |
Output is correct |
29 |
Correct |
4 ms |
608 KB |
Output is correct |
30 |
Correct |
3 ms |
560 KB |
Output is correct |
31 |
Correct |
3 ms |
596 KB |
Output is correct |
32 |
Correct |
3 ms |
596 KB |
Output is correct |
33 |
Correct |
3 ms |
468 KB |
Output is correct |
34 |
Correct |
2 ms |
560 KB |
Output is correct |
35 |
Correct |
2 ms |
464 KB |
Output is correct |
36 |
Correct |
2 ms |
464 KB |
Output is correct |
37 |
Correct |
3 ms |
724 KB |
Output is correct |
38 |
Correct |
3 ms |
564 KB |
Output is correct |
39 |
Correct |
2 ms |
468 KB |
Output is correct |
40 |
Correct |
2 ms |
468 KB |
Output is correct |
41 |
Correct |
3 ms |
596 KB |
Output is correct |
42 |
Correct |
3 ms |
596 KB |
Output is correct |
43 |
Correct |
2 ms |
724 KB |
Output is correct |
44 |
Correct |
2 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
292 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
292 KB |
Output is correct |
9 |
Correct |
0 ms |
288 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
296 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
3 ms |
468 KB |
Output is correct |
26 |
Correct |
4 ms |
596 KB |
Output is correct |
27 |
Correct |
3 ms |
468 KB |
Output is correct |
28 |
Correct |
3 ms |
596 KB |
Output is correct |
29 |
Correct |
4 ms |
608 KB |
Output is correct |
30 |
Correct |
3 ms |
560 KB |
Output is correct |
31 |
Correct |
3 ms |
596 KB |
Output is correct |
32 |
Correct |
3 ms |
596 KB |
Output is correct |
33 |
Correct |
3 ms |
468 KB |
Output is correct |
34 |
Correct |
2 ms |
560 KB |
Output is correct |
35 |
Correct |
2 ms |
464 KB |
Output is correct |
36 |
Correct |
2 ms |
464 KB |
Output is correct |
37 |
Correct |
3 ms |
724 KB |
Output is correct |
38 |
Correct |
3 ms |
564 KB |
Output is correct |
39 |
Correct |
2 ms |
468 KB |
Output is correct |
40 |
Correct |
2 ms |
468 KB |
Output is correct |
41 |
Correct |
3 ms |
596 KB |
Output is correct |
42 |
Correct |
3 ms |
596 KB |
Output is correct |
43 |
Correct |
2 ms |
724 KB |
Output is correct |
44 |
Correct |
2 ms |
596 KB |
Output is correct |
45 |
Correct |
159 ms |
12464 KB |
Output is correct |
46 |
Correct |
153 ms |
13468 KB |
Output is correct |
47 |
Correct |
184 ms |
11756 KB |
Output is correct |
48 |
Correct |
156 ms |
13436 KB |
Output is correct |
49 |
Correct |
152 ms |
11856 KB |
Output is correct |
50 |
Correct |
173 ms |
14748 KB |
Output is correct |
51 |
Correct |
157 ms |
13268 KB |
Output is correct |
52 |
Correct |
105 ms |
11336 KB |
Output is correct |
53 |
Correct |
184 ms |
11356 KB |
Output is correct |
54 |
Correct |
142 ms |
27000 KB |
Output is correct |
55 |
Correct |
149 ms |
19244 KB |
Output is correct |
56 |
Correct |
149 ms |
19156 KB |
Output is correct |
57 |
Correct |
117 ms |
11356 KB |
Output is correct |
58 |
Correct |
106 ms |
11288 KB |
Output is correct |
59 |
Correct |
152 ms |
11336 KB |
Output is correct |
60 |
Correct |
164 ms |
11352 KB |
Output is correct |
61 |
Correct |
152 ms |
11356 KB |
Output is correct |
62 |
Correct |
130 ms |
11352 KB |
Output is correct |
63 |
Correct |
151 ms |
11276 KB |
Output is correct |
64 |
Correct |
155 ms |
11360 KB |
Output is correct |
65 |
Correct |
209 ms |
27004 KB |
Output is correct |
66 |
Correct |
227 ms |
27068 KB |
Output is correct |
67 |
Correct |
179 ms |
15256 KB |
Output is correct |
68 |
Correct |
164 ms |
15260 KB |
Output is correct |
69 |
Correct |
177 ms |
14840 KB |
Output is correct |
70 |
Correct |
186 ms |
14912 KB |
Output is correct |
71 |
Correct |
172 ms |
19196 KB |
Output is correct |
72 |
Correct |
154 ms |
19180 KB |
Output is correct |
73 |
Correct |
159 ms |
16464 KB |
Output is correct |
74 |
Correct |
145 ms |
16472 KB |
Output is correct |
75 |
Correct |
103 ms |
15900 KB |
Output is correct |
76 |
Correct |
105 ms |
19072 KB |
Output is correct |
77 |
Correct |
118 ms |
26908 KB |
Output is correct |
78 |
Correct |
154 ms |
13252 KB |
Output is correct |
79 |
Correct |
151 ms |
12492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
292 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
0 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
292 KB |
Output is correct |
9 |
Correct |
0 ms |
288 KB |
Output is correct |
10 |
Correct |
0 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
0 ms |
340 KB |
Output is correct |
13 |
Correct |
0 ms |
340 KB |
Output is correct |
14 |
Correct |
0 ms |
296 KB |
Output is correct |
15 |
Correct |
0 ms |
340 KB |
Output is correct |
16 |
Correct |
0 ms |
340 KB |
Output is correct |
17 |
Correct |
0 ms |
340 KB |
Output is correct |
18 |
Correct |
0 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
0 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
0 ms |
340 KB |
Output is correct |
24 |
Correct |
0 ms |
340 KB |
Output is correct |
25 |
Correct |
3 ms |
468 KB |
Output is correct |
26 |
Correct |
4 ms |
596 KB |
Output is correct |
27 |
Correct |
3 ms |
468 KB |
Output is correct |
28 |
Correct |
3 ms |
596 KB |
Output is correct |
29 |
Correct |
4 ms |
608 KB |
Output is correct |
30 |
Correct |
3 ms |
560 KB |
Output is correct |
31 |
Correct |
3 ms |
596 KB |
Output is correct |
32 |
Correct |
3 ms |
596 KB |
Output is correct |
33 |
Correct |
3 ms |
468 KB |
Output is correct |
34 |
Correct |
2 ms |
560 KB |
Output is correct |
35 |
Correct |
2 ms |
464 KB |
Output is correct |
36 |
Correct |
2 ms |
464 KB |
Output is correct |
37 |
Correct |
3 ms |
724 KB |
Output is correct |
38 |
Correct |
3 ms |
564 KB |
Output is correct |
39 |
Correct |
2 ms |
468 KB |
Output is correct |
40 |
Correct |
2 ms |
468 KB |
Output is correct |
41 |
Correct |
3 ms |
596 KB |
Output is correct |
42 |
Correct |
3 ms |
596 KB |
Output is correct |
43 |
Correct |
2 ms |
724 KB |
Output is correct |
44 |
Correct |
2 ms |
596 KB |
Output is correct |
45 |
Correct |
159 ms |
12464 KB |
Output is correct |
46 |
Correct |
153 ms |
13468 KB |
Output is correct |
47 |
Correct |
184 ms |
11756 KB |
Output is correct |
48 |
Correct |
156 ms |
13436 KB |
Output is correct |
49 |
Correct |
152 ms |
11856 KB |
Output is correct |
50 |
Correct |
173 ms |
14748 KB |
Output is correct |
51 |
Correct |
157 ms |
13268 KB |
Output is correct |
52 |
Correct |
105 ms |
11336 KB |
Output is correct |
53 |
Correct |
184 ms |
11356 KB |
Output is correct |
54 |
Correct |
142 ms |
27000 KB |
Output is correct |
55 |
Correct |
149 ms |
19244 KB |
Output is correct |
56 |
Correct |
149 ms |
19156 KB |
Output is correct |
57 |
Correct |
117 ms |
11356 KB |
Output is correct |
58 |
Correct |
106 ms |
11288 KB |
Output is correct |
59 |
Correct |
152 ms |
11336 KB |
Output is correct |
60 |
Correct |
164 ms |
11352 KB |
Output is correct |
61 |
Correct |
152 ms |
11356 KB |
Output is correct |
62 |
Correct |
130 ms |
11352 KB |
Output is correct |
63 |
Correct |
151 ms |
11276 KB |
Output is correct |
64 |
Correct |
155 ms |
11360 KB |
Output is correct |
65 |
Correct |
209 ms |
27004 KB |
Output is correct |
66 |
Correct |
227 ms |
27068 KB |
Output is correct |
67 |
Correct |
179 ms |
15256 KB |
Output is correct |
68 |
Correct |
164 ms |
15260 KB |
Output is correct |
69 |
Correct |
177 ms |
14840 KB |
Output is correct |
70 |
Correct |
186 ms |
14912 KB |
Output is correct |
71 |
Correct |
172 ms |
19196 KB |
Output is correct |
72 |
Correct |
154 ms |
19180 KB |
Output is correct |
73 |
Correct |
159 ms |
16464 KB |
Output is correct |
74 |
Correct |
145 ms |
16472 KB |
Output is correct |
75 |
Correct |
103 ms |
15900 KB |
Output is correct |
76 |
Correct |
105 ms |
19072 KB |
Output is correct |
77 |
Correct |
118 ms |
26908 KB |
Output is correct |
78 |
Correct |
154 ms |
13252 KB |
Output is correct |
79 |
Correct |
151 ms |
12492 KB |
Output is correct |
80 |
Correct |
2110 ms |
101000 KB |
Output is correct |
81 |
Correct |
2158 ms |
100028 KB |
Output is correct |
82 |
Correct |
2129 ms |
96852 KB |
Output is correct |
83 |
Correct |
2112 ms |
100196 KB |
Output is correct |
84 |
Correct |
2147 ms |
101028 KB |
Output is correct |
85 |
Correct |
2128 ms |
97680 KB |
Output is correct |
86 |
Correct |
2126 ms |
100176 KB |
Output is correct |
87 |
Correct |
1806 ms |
96156 KB |
Output is correct |
88 |
Correct |
3261 ms |
96152 KB |
Output is correct |
89 |
Correct |
1974 ms |
252748 KB |
Output is correct |
90 |
Correct |
1924 ms |
174464 KB |
Output is correct |
91 |
Correct |
1927 ms |
174452 KB |
Output is correct |
92 |
Correct |
1965 ms |
96152 KB |
Output is correct |
93 |
Correct |
1805 ms |
96152 KB |
Output is correct |
94 |
Correct |
2582 ms |
96148 KB |
Output is correct |
95 |
Correct |
2291 ms |
96152 KB |
Output is correct |
96 |
Correct |
2121 ms |
96164 KB |
Output is correct |
97 |
Correct |
2424 ms |
96176 KB |
Output is correct |
98 |
Correct |
2160 ms |
96156 KB |
Output is correct |
99 |
Correct |
1949 ms |
96240 KB |
Output is correct |
100 |
Correct |
3427 ms |
252564 KB |
Output is correct |
101 |
Correct |
3468 ms |
252640 KB |
Output is correct |
102 |
Correct |
2248 ms |
135312 KB |
Output is correct |
103 |
Correct |
2218 ms |
135256 KB |
Output is correct |
104 |
Correct |
2189 ms |
130936 KB |
Output is correct |
105 |
Correct |
2170 ms |
130940 KB |
Output is correct |
106 |
Correct |
2133 ms |
174424 KB |
Output is correct |
107 |
Correct |
2123 ms |
174420 KB |
Output is correct |
108 |
Correct |
1968 ms |
148356 KB |
Output is correct |
109 |
Correct |
1960 ms |
148456 KB |
Output is correct |
110 |
Correct |
1510 ms |
172932 KB |
Output is correct |
111 |
Correct |
1540 ms |
174460 KB |
Output is correct |
112 |
Correct |
1580 ms |
252508 KB |
Output is correct |
113 |
Correct |
2170 ms |
96860 KB |
Output is correct |
114 |
Correct |
2160 ms |
99944 KB |
Output is correct |