#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int MOD = 1e9+7;
pair<int, int> operator + (const pair<int, int> &x, const pair<int, int> &y){return pair<int, int>(x.first + y.first, x.second + y.second);}
pair<int, int> operator - (const pair<int, int> &x, const pair<int, int> &y){return pair<int, int>(x.first - y.first, x.second - y.second);}
struct Seg{
pair<int, int> tree[2002000];
int sz;
void init(int n){sz = n;}
void update(int p, int x){
pair<int, int> v(1, x);
while(p<=sz){
tree[p] = tree[p] + v;
p += p&-p;
}
}
pair<int, int> sum(int p){
pair<int, int> ret(0, 0);
while(p){
ret = ret + tree[p];
p -= p&-p;
}
return ret;
}
int query(int l, int r){
auto p = sum(r) - sum(l-1);
if (p.second==0 && p.first) return 1;
else if (p.second==0) return -2;
if (p.second==p.first) return 0;
return -1;
}
}tree;
struct DSU{
int path[2002000], R[2002000], c;
void init(int n){c = n; for (int i=1;i<=n;i++) path[i] = R[i] = i;}
int find(int s){
if (s==path[s]) return s;
return path[s] = find(path[s]);
}
void merge(int s, int v){
s = find(s), v = find(v);
if (s==v) return;
--c;
path[s] = v;
R[v] = max(R[v], R[s]);
}
int r(int x){return R[find(x)];}
}dsu;
vector<int> adj[2002000];
int a[2002000], visited[2002000], col[2002000];
ll pw(ll a, ll e){
if (!e) return 1;
ll ret = pw(a, e/2);
if (e&1) return ret * ret % MOD * a % MOD;
return ret * ret % MOD;
}
void dfs(int s, int pa = 0){
col[a[s]] = col[s];
visited[s] = 1;
for (auto &v:adj[s]) if (v!=pa){
col[v] = col[s] ^ 1;
dfs(v, s);
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int n;
cin >> n;
tree.init(n*2);
dsu.init(n*2);
for (int i=1;i<=n;i++){
int x, y;
cin >> x >> y;
a[x] = y;
a[y] = x;
dsu.merge(x, y);
}
vector<int> st;
for (int i=1;i<=n*2;i++){
while(!st.empty() && st.back() < i) st.pop_back();
if (i < a[i]){
st.push_back(a[i]);
}
else{
int R = dsu.r(i);
while(!st.empty() && st.back() != R){
dsu.merge(i, st.back());
adj[i].push_back(st.back());
adj[st.back()].push_back(i);
st.pop_back();
}
st.back() = dsu.r(i);
}
assert(st.back()==dsu.r(i));
}
for (int i=1;i<=n*2;i++) if (a[i] < i && !visited[i]) dfs(i);
for (int i=1;i<=n*2;i++) if (i < a[i]){
int tmp = tree.query(i, a[i]);
if (tmp!=col[i] && tmp!=-2){
printf("0\n");
return 0;
}
tree.update(a[i], col[i]);
}
printf("%lld\n", pw(2, dsu.c));
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
62924 KB |
Output is correct |
2 |
Correct |
29 ms |
63024 KB |
Output is correct |
3 |
Correct |
28 ms |
63024 KB |
Output is correct |
4 |
Correct |
31 ms |
63032 KB |
Output is correct |
5 |
Correct |
27 ms |
63048 KB |
Output is correct |
6 |
Correct |
28 ms |
62956 KB |
Output is correct |
7 |
Correct |
28 ms |
62932 KB |
Output is correct |
8 |
Correct |
29 ms |
63044 KB |
Output is correct |
9 |
Correct |
28 ms |
62948 KB |
Output is correct |
10 |
Correct |
28 ms |
62960 KB |
Output is correct |
11 |
Correct |
28 ms |
62972 KB |
Output is correct |
12 |
Correct |
28 ms |
63000 KB |
Output is correct |
13 |
Correct |
27 ms |
62912 KB |
Output is correct |
14 |
Correct |
27 ms |
63044 KB |
Output is correct |
15 |
Correct |
28 ms |
62960 KB |
Output is correct |
16 |
Correct |
29 ms |
62960 KB |
Output is correct |
17 |
Correct |
27 ms |
63028 KB |
Output is correct |
18 |
Correct |
29 ms |
63060 KB |
Output is correct |
19 |
Correct |
29 ms |
62984 KB |
Output is correct |
20 |
Correct |
29 ms |
62988 KB |
Output is correct |
21 |
Correct |
28 ms |
63056 KB |
Output is correct |
22 |
Correct |
32 ms |
62924 KB |
Output is correct |
23 |
Correct |
27 ms |
62932 KB |
Output is correct |
24 |
Correct |
29 ms |
62916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
62924 KB |
Output is correct |
2 |
Correct |
29 ms |
63024 KB |
Output is correct |
3 |
Correct |
28 ms |
63024 KB |
Output is correct |
4 |
Correct |
31 ms |
63032 KB |
Output is correct |
5 |
Correct |
27 ms |
63048 KB |
Output is correct |
6 |
Correct |
28 ms |
62956 KB |
Output is correct |
7 |
Correct |
28 ms |
62932 KB |
Output is correct |
8 |
Correct |
29 ms |
63044 KB |
Output is correct |
9 |
Correct |
28 ms |
62948 KB |
Output is correct |
10 |
Correct |
28 ms |
62960 KB |
Output is correct |
11 |
Correct |
28 ms |
62972 KB |
Output is correct |
12 |
Correct |
28 ms |
63000 KB |
Output is correct |
13 |
Correct |
27 ms |
62912 KB |
Output is correct |
14 |
Correct |
27 ms |
63044 KB |
Output is correct |
15 |
Correct |
28 ms |
62960 KB |
Output is correct |
16 |
Correct |
29 ms |
62960 KB |
Output is correct |
17 |
Correct |
27 ms |
63028 KB |
Output is correct |
18 |
Correct |
29 ms |
63060 KB |
Output is correct |
19 |
Correct |
29 ms |
62984 KB |
Output is correct |
20 |
Correct |
29 ms |
62988 KB |
Output is correct |
21 |
Correct |
28 ms |
63056 KB |
Output is correct |
22 |
Correct |
32 ms |
62924 KB |
Output is correct |
23 |
Correct |
27 ms |
62932 KB |
Output is correct |
24 |
Correct |
29 ms |
62916 KB |
Output is correct |
25 |
Correct |
32 ms |
63148 KB |
Output is correct |
26 |
Correct |
29 ms |
63212 KB |
Output is correct |
27 |
Correct |
29 ms |
63168 KB |
Output is correct |
28 |
Correct |
29 ms |
63172 KB |
Output is correct |
29 |
Correct |
28 ms |
63188 KB |
Output is correct |
30 |
Correct |
29 ms |
63160 KB |
Output is correct |
31 |
Correct |
29 ms |
63152 KB |
Output is correct |
32 |
Correct |
29 ms |
63180 KB |
Output is correct |
33 |
Correct |
28 ms |
63188 KB |
Output is correct |
34 |
Correct |
28 ms |
63196 KB |
Output is correct |
35 |
Correct |
28 ms |
63100 KB |
Output is correct |
36 |
Correct |
28 ms |
63116 KB |
Output is correct |
37 |
Correct |
28 ms |
63108 KB |
Output is correct |
38 |
Correct |
30 ms |
63208 KB |
Output is correct |
39 |
Correct |
28 ms |
63188 KB |
Output is correct |
40 |
Correct |
28 ms |
63104 KB |
Output is correct |
41 |
Correct |
28 ms |
63144 KB |
Output is correct |
42 |
Correct |
28 ms |
63216 KB |
Output is correct |
43 |
Correct |
30 ms |
63276 KB |
Output is correct |
44 |
Correct |
30 ms |
63300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
62924 KB |
Output is correct |
2 |
Correct |
29 ms |
63024 KB |
Output is correct |
3 |
Correct |
28 ms |
63024 KB |
Output is correct |
4 |
Correct |
31 ms |
63032 KB |
Output is correct |
5 |
Correct |
27 ms |
63048 KB |
Output is correct |
6 |
Correct |
28 ms |
62956 KB |
Output is correct |
7 |
Correct |
28 ms |
62932 KB |
Output is correct |
8 |
Correct |
29 ms |
63044 KB |
Output is correct |
9 |
Correct |
28 ms |
62948 KB |
Output is correct |
10 |
Correct |
28 ms |
62960 KB |
Output is correct |
11 |
Correct |
28 ms |
62972 KB |
Output is correct |
12 |
Correct |
28 ms |
63000 KB |
Output is correct |
13 |
Correct |
27 ms |
62912 KB |
Output is correct |
14 |
Correct |
27 ms |
63044 KB |
Output is correct |
15 |
Correct |
28 ms |
62960 KB |
Output is correct |
16 |
Correct |
29 ms |
62960 KB |
Output is correct |
17 |
Correct |
27 ms |
63028 KB |
Output is correct |
18 |
Correct |
29 ms |
63060 KB |
Output is correct |
19 |
Correct |
29 ms |
62984 KB |
Output is correct |
20 |
Correct |
29 ms |
62988 KB |
Output is correct |
21 |
Correct |
28 ms |
63056 KB |
Output is correct |
22 |
Correct |
32 ms |
62924 KB |
Output is correct |
23 |
Correct |
27 ms |
62932 KB |
Output is correct |
24 |
Correct |
29 ms |
62916 KB |
Output is correct |
25 |
Correct |
32 ms |
63148 KB |
Output is correct |
26 |
Correct |
29 ms |
63212 KB |
Output is correct |
27 |
Correct |
29 ms |
63168 KB |
Output is correct |
28 |
Correct |
29 ms |
63172 KB |
Output is correct |
29 |
Correct |
28 ms |
63188 KB |
Output is correct |
30 |
Correct |
29 ms |
63160 KB |
Output is correct |
31 |
Correct |
29 ms |
63152 KB |
Output is correct |
32 |
Correct |
29 ms |
63180 KB |
Output is correct |
33 |
Correct |
28 ms |
63188 KB |
Output is correct |
34 |
Correct |
28 ms |
63196 KB |
Output is correct |
35 |
Correct |
28 ms |
63100 KB |
Output is correct |
36 |
Correct |
28 ms |
63116 KB |
Output is correct |
37 |
Correct |
28 ms |
63108 KB |
Output is correct |
38 |
Correct |
30 ms |
63208 KB |
Output is correct |
39 |
Correct |
28 ms |
63188 KB |
Output is correct |
40 |
Correct |
28 ms |
63104 KB |
Output is correct |
41 |
Correct |
28 ms |
63144 KB |
Output is correct |
42 |
Correct |
28 ms |
63216 KB |
Output is correct |
43 |
Correct |
30 ms |
63276 KB |
Output is correct |
44 |
Correct |
30 ms |
63300 KB |
Output is correct |
45 |
Correct |
68 ms |
71376 KB |
Output is correct |
46 |
Correct |
72 ms |
71756 KB |
Output is correct |
47 |
Correct |
70 ms |
71108 KB |
Output is correct |
48 |
Correct |
73 ms |
71704 KB |
Output is correct |
49 |
Correct |
73 ms |
71080 KB |
Output is correct |
50 |
Correct |
65 ms |
71608 KB |
Output is correct |
51 |
Correct |
68 ms |
71628 KB |
Output is correct |
52 |
Correct |
56 ms |
68164 KB |
Output is correct |
53 |
Correct |
64 ms |
67916 KB |
Output is correct |
54 |
Correct |
62 ms |
71708 KB |
Output is correct |
55 |
Correct |
58 ms |
71500 KB |
Output is correct |
56 |
Correct |
59 ms |
71492 KB |
Output is correct |
57 |
Correct |
59 ms |
71260 KB |
Output is correct |
58 |
Correct |
54 ms |
68180 KB |
Output is correct |
59 |
Correct |
58 ms |
68804 KB |
Output is correct |
60 |
Correct |
65 ms |
70172 KB |
Output is correct |
61 |
Correct |
69 ms |
70724 KB |
Output is correct |
62 |
Correct |
55 ms |
70072 KB |
Output is correct |
63 |
Correct |
60 ms |
70448 KB |
Output is correct |
64 |
Correct |
62 ms |
70840 KB |
Output is correct |
65 |
Correct |
78 ms |
71840 KB |
Output is correct |
66 |
Correct |
74 ms |
71648 KB |
Output is correct |
67 |
Correct |
65 ms |
71500 KB |
Output is correct |
68 |
Correct |
67 ms |
71596 KB |
Output is correct |
69 |
Correct |
65 ms |
71628 KB |
Output is correct |
70 |
Correct |
68 ms |
71516 KB |
Output is correct |
71 |
Correct |
63 ms |
72268 KB |
Output is correct |
72 |
Correct |
63 ms |
72384 KB |
Output is correct |
73 |
Correct |
61 ms |
72644 KB |
Output is correct |
74 |
Correct |
61 ms |
72644 KB |
Output is correct |
75 |
Correct |
68 ms |
77508 KB |
Output is correct |
76 |
Correct |
66 ms |
77516 KB |
Output is correct |
77 |
Correct |
77 ms |
77476 KB |
Output is correct |
78 |
Correct |
89 ms |
71660 KB |
Output is correct |
79 |
Correct |
82 ms |
71360 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
62924 KB |
Output is correct |
2 |
Correct |
29 ms |
63024 KB |
Output is correct |
3 |
Correct |
28 ms |
63024 KB |
Output is correct |
4 |
Correct |
31 ms |
63032 KB |
Output is correct |
5 |
Correct |
27 ms |
63048 KB |
Output is correct |
6 |
Correct |
28 ms |
62956 KB |
Output is correct |
7 |
Correct |
28 ms |
62932 KB |
Output is correct |
8 |
Correct |
29 ms |
63044 KB |
Output is correct |
9 |
Correct |
28 ms |
62948 KB |
Output is correct |
10 |
Correct |
28 ms |
62960 KB |
Output is correct |
11 |
Correct |
28 ms |
62972 KB |
Output is correct |
12 |
Correct |
28 ms |
63000 KB |
Output is correct |
13 |
Correct |
27 ms |
62912 KB |
Output is correct |
14 |
Correct |
27 ms |
63044 KB |
Output is correct |
15 |
Correct |
28 ms |
62960 KB |
Output is correct |
16 |
Correct |
29 ms |
62960 KB |
Output is correct |
17 |
Correct |
27 ms |
63028 KB |
Output is correct |
18 |
Correct |
29 ms |
63060 KB |
Output is correct |
19 |
Correct |
29 ms |
62984 KB |
Output is correct |
20 |
Correct |
29 ms |
62988 KB |
Output is correct |
21 |
Correct |
28 ms |
63056 KB |
Output is correct |
22 |
Correct |
32 ms |
62924 KB |
Output is correct |
23 |
Correct |
27 ms |
62932 KB |
Output is correct |
24 |
Correct |
29 ms |
62916 KB |
Output is correct |
25 |
Correct |
32 ms |
63148 KB |
Output is correct |
26 |
Correct |
29 ms |
63212 KB |
Output is correct |
27 |
Correct |
29 ms |
63168 KB |
Output is correct |
28 |
Correct |
29 ms |
63172 KB |
Output is correct |
29 |
Correct |
28 ms |
63188 KB |
Output is correct |
30 |
Correct |
29 ms |
63160 KB |
Output is correct |
31 |
Correct |
29 ms |
63152 KB |
Output is correct |
32 |
Correct |
29 ms |
63180 KB |
Output is correct |
33 |
Correct |
28 ms |
63188 KB |
Output is correct |
34 |
Correct |
28 ms |
63196 KB |
Output is correct |
35 |
Correct |
28 ms |
63100 KB |
Output is correct |
36 |
Correct |
28 ms |
63116 KB |
Output is correct |
37 |
Correct |
28 ms |
63108 KB |
Output is correct |
38 |
Correct |
30 ms |
63208 KB |
Output is correct |
39 |
Correct |
28 ms |
63188 KB |
Output is correct |
40 |
Correct |
28 ms |
63104 KB |
Output is correct |
41 |
Correct |
28 ms |
63144 KB |
Output is correct |
42 |
Correct |
28 ms |
63216 KB |
Output is correct |
43 |
Correct |
30 ms |
63276 KB |
Output is correct |
44 |
Correct |
30 ms |
63300 KB |
Output is correct |
45 |
Correct |
68 ms |
71376 KB |
Output is correct |
46 |
Correct |
72 ms |
71756 KB |
Output is correct |
47 |
Correct |
70 ms |
71108 KB |
Output is correct |
48 |
Correct |
73 ms |
71704 KB |
Output is correct |
49 |
Correct |
73 ms |
71080 KB |
Output is correct |
50 |
Correct |
65 ms |
71608 KB |
Output is correct |
51 |
Correct |
68 ms |
71628 KB |
Output is correct |
52 |
Correct |
56 ms |
68164 KB |
Output is correct |
53 |
Correct |
64 ms |
67916 KB |
Output is correct |
54 |
Correct |
62 ms |
71708 KB |
Output is correct |
55 |
Correct |
58 ms |
71500 KB |
Output is correct |
56 |
Correct |
59 ms |
71492 KB |
Output is correct |
57 |
Correct |
59 ms |
71260 KB |
Output is correct |
58 |
Correct |
54 ms |
68180 KB |
Output is correct |
59 |
Correct |
58 ms |
68804 KB |
Output is correct |
60 |
Correct |
65 ms |
70172 KB |
Output is correct |
61 |
Correct |
69 ms |
70724 KB |
Output is correct |
62 |
Correct |
55 ms |
70072 KB |
Output is correct |
63 |
Correct |
60 ms |
70448 KB |
Output is correct |
64 |
Correct |
62 ms |
70840 KB |
Output is correct |
65 |
Correct |
78 ms |
71840 KB |
Output is correct |
66 |
Correct |
74 ms |
71648 KB |
Output is correct |
67 |
Correct |
65 ms |
71500 KB |
Output is correct |
68 |
Correct |
67 ms |
71596 KB |
Output is correct |
69 |
Correct |
65 ms |
71628 KB |
Output is correct |
70 |
Correct |
68 ms |
71516 KB |
Output is correct |
71 |
Correct |
63 ms |
72268 KB |
Output is correct |
72 |
Correct |
63 ms |
72384 KB |
Output is correct |
73 |
Correct |
61 ms |
72644 KB |
Output is correct |
74 |
Correct |
61 ms |
72644 KB |
Output is correct |
75 |
Correct |
68 ms |
77508 KB |
Output is correct |
76 |
Correct |
66 ms |
77516 KB |
Output is correct |
77 |
Correct |
77 ms |
77476 KB |
Output is correct |
78 |
Correct |
89 ms |
71660 KB |
Output is correct |
79 |
Correct |
82 ms |
71360 KB |
Output is correct |
80 |
Correct |
747 ms |
146400 KB |
Output is correct |
81 |
Correct |
671 ms |
145868 KB |
Output is correct |
82 |
Correct |
622 ms |
144660 KB |
Output is correct |
83 |
Correct |
625 ms |
146136 KB |
Output is correct |
84 |
Correct |
662 ms |
146376 KB |
Output is correct |
85 |
Correct |
611 ms |
145376 KB |
Output is correct |
86 |
Correct |
659 ms |
146132 KB |
Output is correct |
87 |
Correct |
489 ms |
116644 KB |
Output is correct |
88 |
Correct |
574 ms |
112860 KB |
Output is correct |
89 |
Correct |
551 ms |
151884 KB |
Output is correct |
90 |
Correct |
558 ms |
149972 KB |
Output is correct |
91 |
Correct |
564 ms |
149976 KB |
Output is correct |
92 |
Correct |
545 ms |
147932 KB |
Output is correct |
93 |
Correct |
496 ms |
116964 KB |
Output is correct |
94 |
Correct |
569 ms |
129720 KB |
Output is correct |
95 |
Correct |
735 ms |
141096 KB |
Output is correct |
96 |
Correct |
637 ms |
143572 KB |
Output is correct |
97 |
Correct |
511 ms |
135572 KB |
Output is correct |
98 |
Correct |
583 ms |
142708 KB |
Output is correct |
99 |
Correct |
587 ms |
147196 KB |
Output is correct |
100 |
Correct |
1048 ms |
152608 KB |
Output is correct |
101 |
Correct |
1031 ms |
152988 KB |
Output is correct |
102 |
Correct |
612 ms |
150668 KB |
Output is correct |
103 |
Correct |
605 ms |
150560 KB |
Output is correct |
104 |
Correct |
610 ms |
150720 KB |
Output is correct |
105 |
Correct |
613 ms |
150836 KB |
Output is correct |
106 |
Correct |
591 ms |
158520 KB |
Output is correct |
107 |
Correct |
593 ms |
158516 KB |
Output is correct |
108 |
Correct |
582 ms |
160568 KB |
Output is correct |
109 |
Correct |
591 ms |
160724 KB |
Output is correct |
110 |
Correct |
579 ms |
210644 KB |
Output is correct |
111 |
Correct |
625 ms |
210648 KB |
Output is correct |
112 |
Correct |
602 ms |
210628 KB |
Output is correct |
113 |
Correct |
647 ms |
144808 KB |
Output is correct |
114 |
Correct |
648 ms |
145764 KB |
Output is correct |