#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'
const int MOD = 1e9+7, MAXN = 1e6, INF = 1e18;
struct SegmentTree{
using T = array<int, 2>;
vector<T> a; int sz = 1; T ID = {-INF, -1};
void init(vector<T> &v){
while(sz < (int)v.size()) sz += sz;
a.assign(2*sz, ID);
build(v, 0, 0, sz);
}
void build(vector<T> &v, int x, int lx, int rx){
if(rx-lx==1){
if(lx < (int)v.size()) a[x] = v[lx];
return;
}
int mx = (lx + rx) / 2;
build(v, 2*x+1, lx, mx);
build(v, 2*x+2, mx, rx);
a[x] = max(a[2*x+1], a[2*x+2]);
}
void update(int i, int x, int lx, int rx){
if(rx-lx==1) return void(a[x] = ID);
int mx = (lx + rx) / 2;
if(i < mx) update(i, 2*x+1, lx, mx);
else update(i, 2*x+2, mx, rx);
a[x] = max(a[2*x+1], a[2*x+2]);
}
void update(int i){ update(i, 0, 0, sz); }
T rangeMax(int l, int r, int x, int lx, int rx){
if(r<=lx || rx<=l) return ID;
if(l<=lx && rx<=r) return a[x];
int mx = (lx + rx) / 2;
return max(rangeMax(l, r, 2*x+1, lx, mx), rangeMax(l, r, 2*x+2, mx, rx));
}
T rangeMax(int l, int r){ return rangeMax(l, r+1, 0, 0, sz); }
} st0, st1;
bitset<MAXN> vis, c;
int a[MAXN], b[MAXN];
void dfs(int u){
int v;
vis[u] = 1;
st0.update(a[u]);
st1.update(b[u]);
while((v = st0.rangeMax(a[u], b[u])[1]) >= 0){
if(b[v] < b[u]) break;
c[v] = c[u] ^ 1;
dfs(v);
}
while((v = st1.rangeMax(a[u], b[u])[1]) >= 0){
if(a[v] > a[u]) break;
c[v] = c[u] ^ 1;
dfs(v);
}
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n; cin >> n;
int s[n+n];
vector<array<int, 2>> v0(n+n, {-INF, -1}), v1(n+n, {-INF, -1});
for(int i=0; i<n; ++i){
cin >> a[i] >> b[i]; --a[i], --b[i];
s[a[i]] = s[b[i]] = i;
v0[a[i]] = {b[i], i};
v1[b[i]] = {-a[i], i};
}
st0.init(v0), st1.init(v1);
int cnt = 1;
for(int i=0; i<n; ++i){
if(vis[i]) continue;
cnt = (cnt + cnt) % MOD;
dfs(i);
}
vector<int> curr[2];
for(int i=0; i<n+n; ++i){
int j = s[i];
if(a[j] == i){
curr[c[j]].push_back(j);
}else{
if(curr[c[j]].back() != j){
cout << 0;
return 0;
}else curr[c[j]].pop_back();
}
}
cout << cnt;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
328 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
328 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
4 ms |
972 KB |
Output is correct |
26 |
Correct |
4 ms |
972 KB |
Output is correct |
27 |
Correct |
4 ms |
972 KB |
Output is correct |
28 |
Correct |
4 ms |
972 KB |
Output is correct |
29 |
Correct |
4 ms |
972 KB |
Output is correct |
30 |
Correct |
4 ms |
972 KB |
Output is correct |
31 |
Correct |
4 ms |
972 KB |
Output is correct |
32 |
Correct |
4 ms |
976 KB |
Output is correct |
33 |
Correct |
4 ms |
856 KB |
Output is correct |
34 |
Correct |
4 ms |
980 KB |
Output is correct |
35 |
Correct |
3 ms |
716 KB |
Output is correct |
36 |
Correct |
3 ms |
716 KB |
Output is correct |
37 |
Correct |
4 ms |
1100 KB |
Output is correct |
38 |
Correct |
3 ms |
972 KB |
Output is correct |
39 |
Correct |
3 ms |
780 KB |
Output is correct |
40 |
Correct |
3 ms |
716 KB |
Output is correct |
41 |
Correct |
4 ms |
1100 KB |
Output is correct |
42 |
Correct |
3 ms |
1100 KB |
Output is correct |
43 |
Correct |
3 ms |
1076 KB |
Output is correct |
44 |
Correct |
3 ms |
1100 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
328 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
4 ms |
972 KB |
Output is correct |
26 |
Correct |
4 ms |
972 KB |
Output is correct |
27 |
Correct |
4 ms |
972 KB |
Output is correct |
28 |
Correct |
4 ms |
972 KB |
Output is correct |
29 |
Correct |
4 ms |
972 KB |
Output is correct |
30 |
Correct |
4 ms |
972 KB |
Output is correct |
31 |
Correct |
4 ms |
972 KB |
Output is correct |
32 |
Correct |
4 ms |
976 KB |
Output is correct |
33 |
Correct |
4 ms |
856 KB |
Output is correct |
34 |
Correct |
4 ms |
980 KB |
Output is correct |
35 |
Correct |
3 ms |
716 KB |
Output is correct |
36 |
Correct |
3 ms |
716 KB |
Output is correct |
37 |
Correct |
4 ms |
1100 KB |
Output is correct |
38 |
Correct |
3 ms |
972 KB |
Output is correct |
39 |
Correct |
3 ms |
780 KB |
Output is correct |
40 |
Correct |
3 ms |
716 KB |
Output is correct |
41 |
Correct |
4 ms |
1100 KB |
Output is correct |
42 |
Correct |
3 ms |
1100 KB |
Output is correct |
43 |
Correct |
3 ms |
1076 KB |
Output is correct |
44 |
Correct |
3 ms |
1100 KB |
Output is correct |
45 |
Correct |
207 ms |
30420 KB |
Output is correct |
46 |
Correct |
209 ms |
32720 KB |
Output is correct |
47 |
Correct |
202 ms |
28800 KB |
Output is correct |
48 |
Correct |
189 ms |
32644 KB |
Output is correct |
49 |
Correct |
187 ms |
29240 KB |
Output is correct |
50 |
Correct |
194 ms |
32020 KB |
Output is correct |
51 |
Correct |
188 ms |
31952 KB |
Output is correct |
52 |
Correct |
148 ms |
27300 KB |
Output is correct |
53 |
Correct |
227 ms |
28564 KB |
Output is correct |
54 |
Correct |
198 ms |
45764 KB |
Output is correct |
55 |
Correct |
202 ms |
36612 KB |
Output is correct |
56 |
Correct |
199 ms |
36600 KB |
Output is correct |
57 |
Correct |
151 ms |
27444 KB |
Output is correct |
58 |
Correct |
157 ms |
27412 KB |
Output is correct |
59 |
Correct |
198 ms |
27764 KB |
Output is correct |
60 |
Correct |
203 ms |
27824 KB |
Output is correct |
61 |
Correct |
218 ms |
27908 KB |
Output is correct |
62 |
Correct |
175 ms |
27880 KB |
Output is correct |
63 |
Correct |
192 ms |
27588 KB |
Output is correct |
64 |
Correct |
198 ms |
27448 KB |
Output is correct |
65 |
Correct |
295 ms |
45168 KB |
Output is correct |
66 |
Correct |
280 ms |
45228 KB |
Output is correct |
67 |
Correct |
193 ms |
37200 KB |
Output is correct |
68 |
Correct |
196 ms |
37188 KB |
Output is correct |
69 |
Correct |
203 ms |
36428 KB |
Output is correct |
70 |
Correct |
200 ms |
36440 KB |
Output is correct |
71 |
Correct |
196 ms |
45800 KB |
Output is correct |
72 |
Correct |
211 ms |
45764 KB |
Output is correct |
73 |
Correct |
185 ms |
40332 KB |
Output is correct |
74 |
Correct |
205 ms |
40392 KB |
Output is correct |
75 |
Correct |
142 ms |
37684 KB |
Output is correct |
76 |
Correct |
138 ms |
44612 KB |
Output is correct |
77 |
Correct |
175 ms |
44596 KB |
Output is correct |
78 |
Correct |
192 ms |
32192 KB |
Output is correct |
79 |
Correct |
193 ms |
30616 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
328 KB |
Output is correct |
7 |
Correct |
1 ms |
332 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
1 ms |
332 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
332 KB |
Output is correct |
13 |
Correct |
1 ms |
332 KB |
Output is correct |
14 |
Correct |
1 ms |
332 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
332 KB |
Output is correct |
18 |
Correct |
1 ms |
332 KB |
Output is correct |
19 |
Correct |
1 ms |
332 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
332 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
4 ms |
972 KB |
Output is correct |
26 |
Correct |
4 ms |
972 KB |
Output is correct |
27 |
Correct |
4 ms |
972 KB |
Output is correct |
28 |
Correct |
4 ms |
972 KB |
Output is correct |
29 |
Correct |
4 ms |
972 KB |
Output is correct |
30 |
Correct |
4 ms |
972 KB |
Output is correct |
31 |
Correct |
4 ms |
972 KB |
Output is correct |
32 |
Correct |
4 ms |
976 KB |
Output is correct |
33 |
Correct |
4 ms |
856 KB |
Output is correct |
34 |
Correct |
4 ms |
980 KB |
Output is correct |
35 |
Correct |
3 ms |
716 KB |
Output is correct |
36 |
Correct |
3 ms |
716 KB |
Output is correct |
37 |
Correct |
4 ms |
1100 KB |
Output is correct |
38 |
Correct |
3 ms |
972 KB |
Output is correct |
39 |
Correct |
3 ms |
780 KB |
Output is correct |
40 |
Correct |
3 ms |
716 KB |
Output is correct |
41 |
Correct |
4 ms |
1100 KB |
Output is correct |
42 |
Correct |
3 ms |
1100 KB |
Output is correct |
43 |
Correct |
3 ms |
1076 KB |
Output is correct |
44 |
Correct |
3 ms |
1100 KB |
Output is correct |
45 |
Correct |
207 ms |
30420 KB |
Output is correct |
46 |
Correct |
209 ms |
32720 KB |
Output is correct |
47 |
Correct |
202 ms |
28800 KB |
Output is correct |
48 |
Correct |
189 ms |
32644 KB |
Output is correct |
49 |
Correct |
187 ms |
29240 KB |
Output is correct |
50 |
Correct |
194 ms |
32020 KB |
Output is correct |
51 |
Correct |
188 ms |
31952 KB |
Output is correct |
52 |
Correct |
148 ms |
27300 KB |
Output is correct |
53 |
Correct |
227 ms |
28564 KB |
Output is correct |
54 |
Correct |
198 ms |
45764 KB |
Output is correct |
55 |
Correct |
202 ms |
36612 KB |
Output is correct |
56 |
Correct |
199 ms |
36600 KB |
Output is correct |
57 |
Correct |
151 ms |
27444 KB |
Output is correct |
58 |
Correct |
157 ms |
27412 KB |
Output is correct |
59 |
Correct |
198 ms |
27764 KB |
Output is correct |
60 |
Correct |
203 ms |
27824 KB |
Output is correct |
61 |
Correct |
218 ms |
27908 KB |
Output is correct |
62 |
Correct |
175 ms |
27880 KB |
Output is correct |
63 |
Correct |
192 ms |
27588 KB |
Output is correct |
64 |
Correct |
198 ms |
27448 KB |
Output is correct |
65 |
Correct |
295 ms |
45168 KB |
Output is correct |
66 |
Correct |
280 ms |
45228 KB |
Output is correct |
67 |
Correct |
193 ms |
37200 KB |
Output is correct |
68 |
Correct |
196 ms |
37188 KB |
Output is correct |
69 |
Correct |
203 ms |
36428 KB |
Output is correct |
70 |
Correct |
200 ms |
36440 KB |
Output is correct |
71 |
Correct |
196 ms |
45800 KB |
Output is correct |
72 |
Correct |
211 ms |
45764 KB |
Output is correct |
73 |
Correct |
185 ms |
40332 KB |
Output is correct |
74 |
Correct |
205 ms |
40392 KB |
Output is correct |
75 |
Correct |
142 ms |
37684 KB |
Output is correct |
76 |
Correct |
138 ms |
44612 KB |
Output is correct |
77 |
Correct |
175 ms |
44596 KB |
Output is correct |
78 |
Correct |
192 ms |
32192 KB |
Output is correct |
79 |
Correct |
193 ms |
30616 KB |
Output is correct |
80 |
Correct |
2364 ms |
255120 KB |
Output is correct |
81 |
Correct |
2336 ms |
253072 KB |
Output is correct |
82 |
Correct |
2368 ms |
246096 KB |
Output is correct |
83 |
Correct |
2364 ms |
253264 KB |
Output is correct |
84 |
Correct |
2446 ms |
255100 KB |
Output is correct |
85 |
Correct |
2324 ms |
247464 KB |
Output is correct |
86 |
Correct |
2351 ms |
252732 KB |
Output is correct |
87 |
Correct |
1881 ms |
240512 KB |
Output is correct |
88 |
Correct |
3078 ms |
248624 KB |
Output is correct |
89 |
Correct |
2405 ms |
422700 KB |
Output is correct |
90 |
Correct |
2328 ms |
331604 KB |
Output is correct |
91 |
Correct |
2317 ms |
331476 KB |
Output is correct |
92 |
Correct |
1888 ms |
240400 KB |
Output is correct |
93 |
Correct |
2040 ms |
240268 KB |
Output is correct |
94 |
Correct |
2577 ms |
246204 KB |
Output is correct |
95 |
Correct |
2367 ms |
244212 KB |
Output is correct |
96 |
Correct |
2247 ms |
243756 KB |
Output is correct |
97 |
Correct |
2447 ms |
245384 KB |
Output is correct |
98 |
Correct |
2303 ms |
243292 KB |
Output is correct |
99 |
Correct |
2226 ms |
244048 KB |
Output is correct |
100 |
Correct |
3791 ms |
416604 KB |
Output is correct |
101 |
Correct |
3876 ms |
416652 KB |
Output is correct |
102 |
Correct |
2609 ms |
336520 KB |
Output is correct |
103 |
Correct |
2466 ms |
336516 KB |
Output is correct |
104 |
Correct |
2423 ms |
327800 KB |
Output is correct |
105 |
Correct |
2458 ms |
327896 KB |
Output is correct |
106 |
Correct |
2530 ms |
422664 KB |
Output is correct |
107 |
Correct |
2497 ms |
422616 KB |
Output is correct |
108 |
Correct |
2334 ms |
366144 KB |
Output is correct |
109 |
Correct |
2334 ms |
366140 KB |
Output is correct |
110 |
Correct |
1893 ms |
409228 KB |
Output is correct |
111 |
Correct |
1661 ms |
412648 KB |
Output is correct |
112 |
Correct |
1749 ms |
412600 KB |
Output is correct |
113 |
Correct |
2354 ms |
245904 KB |
Output is correct |
114 |
Correct |
2376 ms |
252756 KB |
Output is correct |