#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N = (int)1e6 + 2;
const int inf = (int)1e8;
const int MOD = (int)1e9 + 7;
pii tr[2][N * 4 + 51];
int k;
void update(int tv, int ps, pii nw){
ps += k;
tr[tv][ps] = nw;
ps /= 2;
while(ps > 0){
if(tv == 0) tr[tv][ps] = min(tr[tv][ps * 2], tr[tv][ps * 2 + 1]);
if(tv == 1) tr[tv][ps] = max(tr[tv][ps * 2], tr[tv][ps * 2 + 1]);
ps /= 2;
}
}
pii query(int tv, int cl, int cr){
cl += k;
cr += k;
pii cur = mp(-inf, -1);
if(tv == 0)
cur.fi = inf;
while(cl <= cr){
if(cl % 2 == 1){
if(tv==0) cur = min(cur, tr[tv][cl]);
else cur = max(cur, tr[tv][cl]);
cl ++ ;
}
if(cr % 2 == 0){
if(tv==0) cur = min(cur, tr[tv][cr]);
else cur = max(cur, tr[tv][cr]);
cr -- ;
}
cl /= 2;
cr /= 2;
}
return cur;
}
pii cl[N * 2];
pii cr[N * 2];
pii q[N];
int bit[N];
void dfs(int u, int b){
bit[u] = b;
update(0, q[u].se, mp(inf, -1));
update(1, q[u].fi, mp(-inf, -1));
int l = q[u].fi, r = q[u].se;
pii cur;
while(1){
cur = query(0, l, r);
if(cur.se == -1 || cur.fi >= l)
break;
dfs(cur.se, !b);
}
while(1){
cur = query(1, l, r);
if(cur.se == -1 || cur.fi <= r){
break;
}
dfs(cur.se, !b);
}
}
int sum[2][N * 4];
void upd(int bt, int id, int x){
id += k;
while(id > 0){
sum[bt][id] += x;
id /= 2;
}
}
int qry(int bt, int l, int r){
l += k;
r += k;
int res = 0;
while(l <= r){
if(l % 2 == 1) res += sum[bt][l ++ ];
if(r % 2 == 0) res += sum[bt][r -- ];
l /= 2;
r /= 2;
}
return res;
}
int main(){
fastIO;
for(int i = 0 ; i < N * 2; i ++ )
cl[i] = mp(inf, -1), cr[i] = mp(-inf, -1);
int n;
cin >> n;
k = n * 2;
for(int i = 0 ; i < k ; i ++ ){
update(0, i, mp(+inf, -1));
update(1, i, mp(-inf, -1));
}
for(int i = 0 ; i < n; i ++ ){
cin >> q[i].fi >> q[i].se;
q[i].fi -- ;
q[i].se -- ;
cl[q[i].se] = mp(q[i].fi, i);
cr[q[i].fi] = mp(q[i].se, i);
bit[i] = -1;
update(0, q[i].se, cl[q[i].se]);
update(1, q[i].fi, cr[q[i].fi]);
}
int ans = 1;
for(int i = 0 ; i < k ; i ++ ){
if(bit[i] == -1){
dfs(i, 0);
ans = (ans * 2ll) % MOD;
}
}
for(int i = 0 ; i < n; i ++ ){
upd(bit[i], q[i].se, +1);
}
for(int i = k - 1; i >= 0 ; i -- ){
if(cr[i].se != -1){
upd(bit[cr[i].se], cr[i].fi, -1);
if(qry(bit[cr[i].se], i, cr[i].fi) > 0){
ans = 0;
}
}
}
cout << ans << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
31736 KB |
Output is correct |
2 |
Correct |
27 ms |
31736 KB |
Output is correct |
3 |
Correct |
28 ms |
31736 KB |
Output is correct |
4 |
Correct |
28 ms |
31736 KB |
Output is correct |
5 |
Correct |
29 ms |
31736 KB |
Output is correct |
6 |
Correct |
27 ms |
31736 KB |
Output is correct |
7 |
Correct |
28 ms |
31736 KB |
Output is correct |
8 |
Correct |
27 ms |
31736 KB |
Output is correct |
9 |
Correct |
33 ms |
31736 KB |
Output is correct |
10 |
Correct |
33 ms |
31740 KB |
Output is correct |
11 |
Correct |
28 ms |
31736 KB |
Output is correct |
12 |
Correct |
27 ms |
31736 KB |
Output is correct |
13 |
Correct |
28 ms |
31740 KB |
Output is correct |
14 |
Correct |
27 ms |
31736 KB |
Output is correct |
15 |
Correct |
27 ms |
31608 KB |
Output is correct |
16 |
Correct |
27 ms |
31736 KB |
Output is correct |
17 |
Correct |
28 ms |
31736 KB |
Output is correct |
18 |
Correct |
27 ms |
31736 KB |
Output is correct |
19 |
Correct |
28 ms |
31736 KB |
Output is correct |
20 |
Correct |
27 ms |
31736 KB |
Output is correct |
21 |
Correct |
27 ms |
31736 KB |
Output is correct |
22 |
Correct |
27 ms |
31608 KB |
Output is correct |
23 |
Correct |
27 ms |
31696 KB |
Output is correct |
24 |
Correct |
27 ms |
31736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
31736 KB |
Output is correct |
2 |
Correct |
27 ms |
31736 KB |
Output is correct |
3 |
Correct |
28 ms |
31736 KB |
Output is correct |
4 |
Correct |
28 ms |
31736 KB |
Output is correct |
5 |
Correct |
29 ms |
31736 KB |
Output is correct |
6 |
Correct |
27 ms |
31736 KB |
Output is correct |
7 |
Correct |
28 ms |
31736 KB |
Output is correct |
8 |
Correct |
27 ms |
31736 KB |
Output is correct |
9 |
Correct |
33 ms |
31736 KB |
Output is correct |
10 |
Correct |
33 ms |
31740 KB |
Output is correct |
11 |
Correct |
28 ms |
31736 KB |
Output is correct |
12 |
Correct |
27 ms |
31736 KB |
Output is correct |
13 |
Correct |
28 ms |
31740 KB |
Output is correct |
14 |
Correct |
27 ms |
31736 KB |
Output is correct |
15 |
Correct |
27 ms |
31608 KB |
Output is correct |
16 |
Correct |
27 ms |
31736 KB |
Output is correct |
17 |
Correct |
28 ms |
31736 KB |
Output is correct |
18 |
Correct |
27 ms |
31736 KB |
Output is correct |
19 |
Correct |
28 ms |
31736 KB |
Output is correct |
20 |
Correct |
27 ms |
31736 KB |
Output is correct |
21 |
Correct |
27 ms |
31736 KB |
Output is correct |
22 |
Correct |
27 ms |
31608 KB |
Output is correct |
23 |
Correct |
27 ms |
31696 KB |
Output is correct |
24 |
Correct |
27 ms |
31736 KB |
Output is correct |
25 |
Correct |
30 ms |
31992 KB |
Output is correct |
26 |
Correct |
31 ms |
31992 KB |
Output is correct |
27 |
Correct |
30 ms |
31992 KB |
Output is correct |
28 |
Correct |
31 ms |
32144 KB |
Output is correct |
29 |
Correct |
31 ms |
31992 KB |
Output is correct |
30 |
Correct |
30 ms |
31992 KB |
Output is correct |
31 |
Correct |
32 ms |
32092 KB |
Output is correct |
32 |
Correct |
31 ms |
31948 KB |
Output is correct |
33 |
Correct |
30 ms |
31992 KB |
Output is correct |
34 |
Correct |
31 ms |
31992 KB |
Output is correct |
35 |
Correct |
29 ms |
31864 KB |
Output is correct |
36 |
Correct |
30 ms |
31864 KB |
Output is correct |
37 |
Correct |
31 ms |
32120 KB |
Output is correct |
38 |
Correct |
30 ms |
31992 KB |
Output is correct |
39 |
Correct |
29 ms |
31864 KB |
Output is correct |
40 |
Correct |
29 ms |
31864 KB |
Output is correct |
41 |
Correct |
30 ms |
32120 KB |
Output is correct |
42 |
Correct |
30 ms |
32120 KB |
Output is correct |
43 |
Correct |
29 ms |
32120 KB |
Output is correct |
44 |
Correct |
30 ms |
32120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
31736 KB |
Output is correct |
2 |
Correct |
27 ms |
31736 KB |
Output is correct |
3 |
Correct |
28 ms |
31736 KB |
Output is correct |
4 |
Correct |
28 ms |
31736 KB |
Output is correct |
5 |
Correct |
29 ms |
31736 KB |
Output is correct |
6 |
Correct |
27 ms |
31736 KB |
Output is correct |
7 |
Correct |
28 ms |
31736 KB |
Output is correct |
8 |
Correct |
27 ms |
31736 KB |
Output is correct |
9 |
Correct |
33 ms |
31736 KB |
Output is correct |
10 |
Correct |
33 ms |
31740 KB |
Output is correct |
11 |
Correct |
28 ms |
31736 KB |
Output is correct |
12 |
Correct |
27 ms |
31736 KB |
Output is correct |
13 |
Correct |
28 ms |
31740 KB |
Output is correct |
14 |
Correct |
27 ms |
31736 KB |
Output is correct |
15 |
Correct |
27 ms |
31608 KB |
Output is correct |
16 |
Correct |
27 ms |
31736 KB |
Output is correct |
17 |
Correct |
28 ms |
31736 KB |
Output is correct |
18 |
Correct |
27 ms |
31736 KB |
Output is correct |
19 |
Correct |
28 ms |
31736 KB |
Output is correct |
20 |
Correct |
27 ms |
31736 KB |
Output is correct |
21 |
Correct |
27 ms |
31736 KB |
Output is correct |
22 |
Correct |
27 ms |
31608 KB |
Output is correct |
23 |
Correct |
27 ms |
31696 KB |
Output is correct |
24 |
Correct |
27 ms |
31736 KB |
Output is correct |
25 |
Correct |
30 ms |
31992 KB |
Output is correct |
26 |
Correct |
31 ms |
31992 KB |
Output is correct |
27 |
Correct |
30 ms |
31992 KB |
Output is correct |
28 |
Correct |
31 ms |
32144 KB |
Output is correct |
29 |
Correct |
31 ms |
31992 KB |
Output is correct |
30 |
Correct |
30 ms |
31992 KB |
Output is correct |
31 |
Correct |
32 ms |
32092 KB |
Output is correct |
32 |
Correct |
31 ms |
31948 KB |
Output is correct |
33 |
Correct |
30 ms |
31992 KB |
Output is correct |
34 |
Correct |
31 ms |
31992 KB |
Output is correct |
35 |
Correct |
29 ms |
31864 KB |
Output is correct |
36 |
Correct |
30 ms |
31864 KB |
Output is correct |
37 |
Correct |
31 ms |
32120 KB |
Output is correct |
38 |
Correct |
30 ms |
31992 KB |
Output is correct |
39 |
Correct |
29 ms |
31864 KB |
Output is correct |
40 |
Correct |
29 ms |
31864 KB |
Output is correct |
41 |
Correct |
30 ms |
32120 KB |
Output is correct |
42 |
Correct |
30 ms |
32120 KB |
Output is correct |
43 |
Correct |
29 ms |
32120 KB |
Output is correct |
44 |
Correct |
30 ms |
32120 KB |
Output is correct |
45 |
Correct |
227 ms |
44552 KB |
Output is correct |
46 |
Correct |
237 ms |
45668 KB |
Output is correct |
47 |
Correct |
229 ms |
43896 KB |
Output is correct |
48 |
Correct |
232 ms |
45688 KB |
Output is correct |
49 |
Correct |
228 ms |
44080 KB |
Output is correct |
50 |
Correct |
234 ms |
45388 KB |
Output is correct |
51 |
Correct |
227 ms |
45496 KB |
Output is correct |
52 |
Correct |
173 ms |
41948 KB |
Output is correct |
53 |
Correct |
215 ms |
41204 KB |
Output is correct |
54 |
Correct |
222 ms |
49116 KB |
Output is correct |
55 |
Correct |
218 ms |
45236 KB |
Output is correct |
56 |
Correct |
218 ms |
45432 KB |
Output is correct |
57 |
Correct |
180 ms |
43640 KB |
Output is correct |
58 |
Correct |
176 ms |
42104 KB |
Output is correct |
59 |
Correct |
209 ms |
43512 KB |
Output is correct |
60 |
Correct |
222 ms |
43548 KB |
Output is correct |
61 |
Correct |
224 ms |
43668 KB |
Output is correct |
62 |
Correct |
210 ms |
43608 KB |
Output is correct |
63 |
Correct |
220 ms |
43512 KB |
Output is correct |
64 |
Correct |
227 ms |
43492 KB |
Output is correct |
65 |
Correct |
302 ms |
50668 KB |
Output is correct |
66 |
Correct |
304 ms |
50596 KB |
Output is correct |
67 |
Correct |
243 ms |
45560 KB |
Output is correct |
68 |
Correct |
241 ms |
45560 KB |
Output is correct |
69 |
Correct |
244 ms |
45304 KB |
Output is correct |
70 |
Correct |
260 ms |
45208 KB |
Output is correct |
71 |
Correct |
234 ms |
49260 KB |
Output is correct |
72 |
Correct |
226 ms |
49016 KB |
Output is correct |
73 |
Correct |
222 ms |
46584 KB |
Output is correct |
74 |
Correct |
220 ms |
46584 KB |
Output is correct |
75 |
Correct |
183 ms |
48184 KB |
Output is correct |
76 |
Correct |
191 ms |
51336 KB |
Output is correct |
77 |
Correct |
218 ms |
51436 KB |
Output is correct |
78 |
Correct |
226 ms |
45468 KB |
Output is correct |
79 |
Correct |
229 ms |
44672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
27 ms |
31736 KB |
Output is correct |
2 |
Correct |
27 ms |
31736 KB |
Output is correct |
3 |
Correct |
28 ms |
31736 KB |
Output is correct |
4 |
Correct |
28 ms |
31736 KB |
Output is correct |
5 |
Correct |
29 ms |
31736 KB |
Output is correct |
6 |
Correct |
27 ms |
31736 KB |
Output is correct |
7 |
Correct |
28 ms |
31736 KB |
Output is correct |
8 |
Correct |
27 ms |
31736 KB |
Output is correct |
9 |
Correct |
33 ms |
31736 KB |
Output is correct |
10 |
Correct |
33 ms |
31740 KB |
Output is correct |
11 |
Correct |
28 ms |
31736 KB |
Output is correct |
12 |
Correct |
27 ms |
31736 KB |
Output is correct |
13 |
Correct |
28 ms |
31740 KB |
Output is correct |
14 |
Correct |
27 ms |
31736 KB |
Output is correct |
15 |
Correct |
27 ms |
31608 KB |
Output is correct |
16 |
Correct |
27 ms |
31736 KB |
Output is correct |
17 |
Correct |
28 ms |
31736 KB |
Output is correct |
18 |
Correct |
27 ms |
31736 KB |
Output is correct |
19 |
Correct |
28 ms |
31736 KB |
Output is correct |
20 |
Correct |
27 ms |
31736 KB |
Output is correct |
21 |
Correct |
27 ms |
31736 KB |
Output is correct |
22 |
Correct |
27 ms |
31608 KB |
Output is correct |
23 |
Correct |
27 ms |
31696 KB |
Output is correct |
24 |
Correct |
27 ms |
31736 KB |
Output is correct |
25 |
Correct |
30 ms |
31992 KB |
Output is correct |
26 |
Correct |
31 ms |
31992 KB |
Output is correct |
27 |
Correct |
30 ms |
31992 KB |
Output is correct |
28 |
Correct |
31 ms |
32144 KB |
Output is correct |
29 |
Correct |
31 ms |
31992 KB |
Output is correct |
30 |
Correct |
30 ms |
31992 KB |
Output is correct |
31 |
Correct |
32 ms |
32092 KB |
Output is correct |
32 |
Correct |
31 ms |
31948 KB |
Output is correct |
33 |
Correct |
30 ms |
31992 KB |
Output is correct |
34 |
Correct |
31 ms |
31992 KB |
Output is correct |
35 |
Correct |
29 ms |
31864 KB |
Output is correct |
36 |
Correct |
30 ms |
31864 KB |
Output is correct |
37 |
Correct |
31 ms |
32120 KB |
Output is correct |
38 |
Correct |
30 ms |
31992 KB |
Output is correct |
39 |
Correct |
29 ms |
31864 KB |
Output is correct |
40 |
Correct |
29 ms |
31864 KB |
Output is correct |
41 |
Correct |
30 ms |
32120 KB |
Output is correct |
42 |
Correct |
30 ms |
32120 KB |
Output is correct |
43 |
Correct |
29 ms |
32120 KB |
Output is correct |
44 |
Correct |
30 ms |
32120 KB |
Output is correct |
45 |
Correct |
227 ms |
44552 KB |
Output is correct |
46 |
Correct |
237 ms |
45668 KB |
Output is correct |
47 |
Correct |
229 ms |
43896 KB |
Output is correct |
48 |
Correct |
232 ms |
45688 KB |
Output is correct |
49 |
Correct |
228 ms |
44080 KB |
Output is correct |
50 |
Correct |
234 ms |
45388 KB |
Output is correct |
51 |
Correct |
227 ms |
45496 KB |
Output is correct |
52 |
Correct |
173 ms |
41948 KB |
Output is correct |
53 |
Correct |
215 ms |
41204 KB |
Output is correct |
54 |
Correct |
222 ms |
49116 KB |
Output is correct |
55 |
Correct |
218 ms |
45236 KB |
Output is correct |
56 |
Correct |
218 ms |
45432 KB |
Output is correct |
57 |
Correct |
180 ms |
43640 KB |
Output is correct |
58 |
Correct |
176 ms |
42104 KB |
Output is correct |
59 |
Correct |
209 ms |
43512 KB |
Output is correct |
60 |
Correct |
222 ms |
43548 KB |
Output is correct |
61 |
Correct |
224 ms |
43668 KB |
Output is correct |
62 |
Correct |
210 ms |
43608 KB |
Output is correct |
63 |
Correct |
220 ms |
43512 KB |
Output is correct |
64 |
Correct |
227 ms |
43492 KB |
Output is correct |
65 |
Correct |
302 ms |
50668 KB |
Output is correct |
66 |
Correct |
304 ms |
50596 KB |
Output is correct |
67 |
Correct |
243 ms |
45560 KB |
Output is correct |
68 |
Correct |
241 ms |
45560 KB |
Output is correct |
69 |
Correct |
244 ms |
45304 KB |
Output is correct |
70 |
Correct |
260 ms |
45208 KB |
Output is correct |
71 |
Correct |
234 ms |
49260 KB |
Output is correct |
72 |
Correct |
226 ms |
49016 KB |
Output is correct |
73 |
Correct |
222 ms |
46584 KB |
Output is correct |
74 |
Correct |
220 ms |
46584 KB |
Output is correct |
75 |
Correct |
183 ms |
48184 KB |
Output is correct |
76 |
Correct |
191 ms |
51336 KB |
Output is correct |
77 |
Correct |
218 ms |
51436 KB |
Output is correct |
78 |
Correct |
226 ms |
45468 KB |
Output is correct |
79 |
Correct |
229 ms |
44672 KB |
Output is correct |
80 |
Correct |
2722 ms |
156740 KB |
Output is correct |
81 |
Correct |
2793 ms |
155780 KB |
Output is correct |
82 |
Correct |
2729 ms |
152576 KB |
Output is correct |
83 |
Correct |
2697 ms |
155988 KB |
Output is correct |
84 |
Correct |
2711 ms |
156708 KB |
Output is correct |
85 |
Correct |
2737 ms |
153324 KB |
Output is correct |
86 |
Correct |
2730 ms |
155872 KB |
Output is correct |
87 |
Correct |
2335 ms |
136416 KB |
Output is correct |
88 |
Correct |
2940 ms |
128584 KB |
Output is correct |
89 |
Correct |
2634 ms |
206928 KB |
Output is correct |
90 |
Correct |
2627 ms |
167892 KB |
Output is correct |
91 |
Correct |
2823 ms |
168036 KB |
Output is correct |
92 |
Correct |
2311 ms |
151932 KB |
Output is correct |
93 |
Correct |
2396 ms |
136412 KB |
Output is correct |
94 |
Correct |
2856 ms |
152100 KB |
Output is correct |
95 |
Correct |
2737 ms |
151848 KB |
Output is correct |
96 |
Correct |
2710 ms |
151888 KB |
Output is correct |
97 |
Correct |
2682 ms |
151908 KB |
Output is correct |
98 |
Correct |
2723 ms |
152024 KB |
Output is correct |
99 |
Correct |
2726 ms |
151948 KB |
Output is correct |
100 |
Correct |
3979 ms |
222656 KB |
Output is correct |
101 |
Correct |
3986 ms |
222568 KB |
Output is correct |
102 |
Correct |
2862 ms |
171532 KB |
Output is correct |
103 |
Correct |
2923 ms |
171684 KB |
Output is correct |
104 |
Correct |
2876 ms |
168592 KB |
Output is correct |
105 |
Correct |
2842 ms |
168724 KB |
Output is correct |
106 |
Correct |
2818 ms |
206924 KB |
Output is correct |
107 |
Correct |
2704 ms |
206920 KB |
Output is correct |
108 |
Correct |
2654 ms |
180852 KB |
Output is correct |
109 |
Correct |
2666 ms |
180780 KB |
Output is correct |
110 |
Correct |
2363 ms |
228728 KB |
Output is correct |
111 |
Correct |
2294 ms |
230264 KB |
Output is correct |
112 |
Correct |
2316 ms |
230204 KB |
Output is correct |
113 |
Correct |
2828 ms |
152752 KB |
Output is correct |
114 |
Correct |
2827 ms |
155588 KB |
Output is correct |