#include "circuit.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "stub.cpp"
#endif
#define ar array
typedef long long ll;
const int N = 1e5 + 5;
const int mod = 1'000'002'022;
int N_;
struct ST{
ar<int, 2> tree[N << 2];
int c[N << 2];
void push(int x, int lx, int rx){
if(lx == rx) return;
if(c[x]){
swap(tree[x << 1][0], tree[x << 1][1]);
swap(tree[x << 1 | 1][0], tree[x << 1 | 1][1]);
c[x << 1] ^= 1, c[x << 1 | 1] ^= 1;
}
c[x] = 0;
}
void set(int i, int v, int lx, int rx, int x){
if(lx == rx){
tree[x][0] = v;
return;
}
push(x, lx, rx);
int m = (lx + rx) >> 1;
if(i <= m) set(i, v, lx, m, x << 1);
else set(i, v, m + 1, rx, x << 1 | 1);
tree[x][0] = (tree[x << 1][0] + tree[x << 1 | 1][0]) % mod;
tree[x][1] = (tree[x << 1][1] + tree[x << 1 | 1][1]) % mod;
}
void set(int i, int v){
set(i, v, 0, N, 1);
}
void togl(int l, int r, int lx, int rx, int x){
if(lx > r || rx < l) return;
if(lx >= l && rx <= r){
c[x] ^= 1;
swap(tree[x][0], tree[x][1]);
return;
}
int m = (lx + rx) >> 1;
push(x, lx, rx);
togl(l, r, lx, m, x << 1);
togl(l, r, m + 1, rx, x << 1 | 1);
tree[x][0] = (tree[x << 1][0] + tree[x << 1 | 1][0]) % mod;
tree[x][1] = (tree[x << 1][1] + tree[x << 1 | 1][1]) % mod;
}
void togl(int l, int r){
togl(l, r, 0, N, 1);
}
}tree;
void init(int n, int m, vector<int> p, vector<int> a) {
vector<vector<int>> edges(n + m);
for(int i=1;i<n+m;i++){
edges[p[i]].push_back(i);
}
vector<int> dp(n + m), up(n + m);
function<void(int)> dfs = [&](int u){
dp[u] = max(1, (int)edges[u].size());
for(auto x : edges[u]){
dfs(x);
dp[u] = dp[u] * 1ll * dp[x] % mod;
}
};
dfs(0);
function<void(int)> re = [&](int u){
int pref = 1;
vector<int> suff(edges[u].size() + 1);
suff.back() = 1;
for(int i=(int)edges[u].size() - 1;~i;i--){
suff[i] = suff[i + 1] * 1ll * dp[edges[u][i]] % mod;
}
for(int i=0;i<(int)edges[u].size();i++){
up[edges[u][i]] = up[u] * 1ll * suff[i + 1] % mod * 1ll * pref % mod;
pref = pref * 1ll * dp[edges[u][i]] % mod;
re(edges[u][i]);
}
};
up[0] = 1;
re(0);
for(int i=n;i<n+m;i++){
tree.set(i - n, up[i]);
}
for(int i=n;i<n+m;i++){
if(a[i - n]) tree.togl(i - n, i - n);
}
N_ = n;
}
int count_ways(int l, int r) {
l -= N_, r -= N_;
tree.togl(l, r);
return tree.tree[1][1];
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
336 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
464 KB |
Output is correct |
7 |
Correct |
1 ms |
464 KB |
Output is correct |
8 |
Correct |
1 ms |
464 KB |
Output is correct |
9 |
Correct |
1 ms |
464 KB |
Output is correct |
10 |
Correct |
1 ms |
632 KB |
Output is correct |
11 |
Correct |
1 ms |
592 KB |
Output is correct |
12 |
Correct |
1 ms |
464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
336 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
1 ms |
336 KB |
Output is correct |
10 |
Correct |
1 ms |
336 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
12 |
Correct |
1 ms |
336 KB |
Output is correct |
13 |
Correct |
1 ms |
336 KB |
Output is correct |
14 |
Correct |
1 ms |
464 KB |
Output is correct |
15 |
Correct |
1 ms |
464 KB |
Output is correct |
16 |
Correct |
1 ms |
464 KB |
Output is correct |
17 |
Correct |
1 ms |
464 KB |
Output is correct |
18 |
Correct |
1 ms |
632 KB |
Output is correct |
19 |
Correct |
1 ms |
592 KB |
Output is correct |
20 |
Correct |
1 ms |
464 KB |
Output is correct |
21 |
Correct |
1 ms |
464 KB |
Output is correct |
22 |
Correct |
1 ms |
464 KB |
Output is correct |
23 |
Correct |
1 ms |
336 KB |
Output is correct |
24 |
Correct |
1 ms |
464 KB |
Output is correct |
25 |
Correct |
1 ms |
464 KB |
Output is correct |
26 |
Correct |
1 ms |
464 KB |
Output is correct |
27 |
Correct |
1 ms |
464 KB |
Output is correct |
28 |
Correct |
1 ms |
464 KB |
Output is correct |
29 |
Correct |
1 ms |
336 KB |
Output is correct |
30 |
Correct |
1 ms |
336 KB |
Output is correct |
31 |
Correct |
1 ms |
464 KB |
Output is correct |
32 |
Correct |
1 ms |
464 KB |
Output is correct |
33 |
Correct |
1 ms |
464 KB |
Output is correct |
34 |
Correct |
2 ms |
464 KB |
Output is correct |
35 |
Correct |
1 ms |
336 KB |
Output is correct |
36 |
Correct |
2 ms |
592 KB |
Output is correct |
37 |
Correct |
1 ms |
592 KB |
Output is correct |
38 |
Correct |
1 ms |
592 KB |
Output is correct |
39 |
Correct |
1 ms |
464 KB |
Output is correct |
40 |
Correct |
1 ms |
464 KB |
Output is correct |
41 |
Correct |
1 ms |
464 KB |
Output is correct |
42 |
Correct |
1 ms |
336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
344 ms |
5164 KB |
Output is correct |
2 |
Correct |
639 ms |
10060 KB |
Output is correct |
3 |
Correct |
575 ms |
10056 KB |
Output is correct |
4 |
Correct |
604 ms |
9652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
344 ms |
5164 KB |
Output is correct |
2 |
Correct |
639 ms |
10060 KB |
Output is correct |
3 |
Correct |
575 ms |
10056 KB |
Output is correct |
4 |
Correct |
604 ms |
9652 KB |
Output is correct |
5 |
Correct |
570 ms |
5192 KB |
Output is correct |
6 |
Correct |
654 ms |
10056 KB |
Output is correct |
7 |
Correct |
619 ms |
10032 KB |
Output is correct |
8 |
Correct |
668 ms |
9996 KB |
Output is correct |
9 |
Correct |
305 ms |
592 KB |
Output is correct |
10 |
Correct |
582 ms |
976 KB |
Output is correct |
11 |
Correct |
596 ms |
976 KB |
Output is correct |
12 |
Correct |
610 ms |
976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
336 KB |
Output is correct |
2 |
Correct |
1 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
464 KB |
Output is correct |
7 |
Correct |
1 ms |
464 KB |
Output is correct |
8 |
Correct |
1 ms |
464 KB |
Output is correct |
9 |
Correct |
1 ms |
464 KB |
Output is correct |
10 |
Correct |
1 ms |
632 KB |
Output is correct |
11 |
Correct |
1 ms |
592 KB |
Output is correct |
12 |
Correct |
1 ms |
464 KB |
Output is correct |
13 |
Correct |
344 ms |
5164 KB |
Output is correct |
14 |
Correct |
639 ms |
10060 KB |
Output is correct |
15 |
Correct |
575 ms |
10056 KB |
Output is correct |
16 |
Correct |
604 ms |
9652 KB |
Output is correct |
17 |
Correct |
570 ms |
5192 KB |
Output is correct |
18 |
Correct |
654 ms |
10056 KB |
Output is correct |
19 |
Correct |
619 ms |
10032 KB |
Output is correct |
20 |
Correct |
668 ms |
9996 KB |
Output is correct |
21 |
Correct |
305 ms |
592 KB |
Output is correct |
22 |
Correct |
582 ms |
976 KB |
Output is correct |
23 |
Correct |
596 ms |
976 KB |
Output is correct |
24 |
Correct |
610 ms |
976 KB |
Output is correct |
25 |
Correct |
617 ms |
14780 KB |
Output is correct |
26 |
Correct |
709 ms |
15124 KB |
Output is correct |
27 |
Correct |
694 ms |
15128 KB |
Output is correct |
28 |
Correct |
498 ms |
15024 KB |
Output is correct |
29 |
Correct |
788 ms |
29244 KB |
Output is correct |
30 |
Correct |
650 ms |
29164 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
336 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
1 ms |
336 KB |
Output is correct |
10 |
Correct |
1 ms |
336 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
12 |
Correct |
1 ms |
336 KB |
Output is correct |
13 |
Correct |
1 ms |
336 KB |
Output is correct |
14 |
Correct |
1 ms |
464 KB |
Output is correct |
15 |
Correct |
1 ms |
464 KB |
Output is correct |
16 |
Correct |
1 ms |
464 KB |
Output is correct |
17 |
Correct |
1 ms |
464 KB |
Output is correct |
18 |
Correct |
1 ms |
632 KB |
Output is correct |
19 |
Correct |
1 ms |
592 KB |
Output is correct |
20 |
Correct |
1 ms |
464 KB |
Output is correct |
21 |
Correct |
1 ms |
464 KB |
Output is correct |
22 |
Correct |
1 ms |
464 KB |
Output is correct |
23 |
Correct |
1 ms |
336 KB |
Output is correct |
24 |
Correct |
1 ms |
464 KB |
Output is correct |
25 |
Correct |
1 ms |
464 KB |
Output is correct |
26 |
Correct |
1 ms |
464 KB |
Output is correct |
27 |
Correct |
1 ms |
464 KB |
Output is correct |
28 |
Correct |
1 ms |
464 KB |
Output is correct |
29 |
Correct |
1 ms |
336 KB |
Output is correct |
30 |
Correct |
1 ms |
336 KB |
Output is correct |
31 |
Correct |
1 ms |
464 KB |
Output is correct |
32 |
Correct |
1 ms |
464 KB |
Output is correct |
33 |
Correct |
1 ms |
464 KB |
Output is correct |
34 |
Correct |
2 ms |
464 KB |
Output is correct |
35 |
Correct |
1 ms |
336 KB |
Output is correct |
36 |
Correct |
2 ms |
592 KB |
Output is correct |
37 |
Correct |
1 ms |
592 KB |
Output is correct |
38 |
Correct |
1 ms |
592 KB |
Output is correct |
39 |
Correct |
1 ms |
464 KB |
Output is correct |
40 |
Correct |
1 ms |
464 KB |
Output is correct |
41 |
Correct |
1 ms |
464 KB |
Output is correct |
42 |
Correct |
1 ms |
336 KB |
Output is correct |
43 |
Correct |
500 ms |
720 KB |
Output is correct |
44 |
Correct |
551 ms |
804 KB |
Output is correct |
45 |
Correct |
622 ms |
844 KB |
Output is correct |
46 |
Correct |
631 ms |
1104 KB |
Output is correct |
47 |
Correct |
593 ms |
1104 KB |
Output is correct |
48 |
Correct |
612 ms |
976 KB |
Output is correct |
49 |
Correct |
668 ms |
1104 KB |
Output is correct |
50 |
Correct |
578 ms |
1104 KB |
Output is correct |
51 |
Correct |
526 ms |
720 KB |
Output is correct |
52 |
Correct |
656 ms |
720 KB |
Output is correct |
53 |
Correct |
530 ms |
1360 KB |
Output is correct |
54 |
Correct |
589 ms |
1104 KB |
Output is correct |
55 |
Correct |
652 ms |
848 KB |
Output is correct |
56 |
Correct |
586 ms |
848 KB |
Output is correct |
57 |
Correct |
516 ms |
720 KB |
Output is correct |
58 |
Correct |
585 ms |
1744 KB |
Output is correct |
59 |
Correct |
599 ms |
1744 KB |
Output is correct |
60 |
Correct |
552 ms |
1872 KB |
Output is correct |
61 |
Correct |
541 ms |
976 KB |
Output is correct |
62 |
Correct |
561 ms |
792 KB |
Output is correct |
63 |
Correct |
663 ms |
740 KB |
Output is correct |
64 |
Correct |
544 ms |
720 KB |
Output is correct |
65 |
Correct |
313 ms |
592 KB |
Output is correct |
66 |
Correct |
661 ms |
976 KB |
Output is correct |
67 |
Correct |
616 ms |
976 KB |
Output is correct |
68 |
Correct |
644 ms |
976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
336 KB |
Output is correct |
2 |
Correct |
0 ms |
336 KB |
Output is correct |
3 |
Correct |
1 ms |
336 KB |
Output is correct |
4 |
Correct |
1 ms |
336 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
336 KB |
Output is correct |
7 |
Correct |
1 ms |
336 KB |
Output is correct |
8 |
Correct |
1 ms |
336 KB |
Output is correct |
9 |
Correct |
1 ms |
336 KB |
Output is correct |
10 |
Correct |
1 ms |
336 KB |
Output is correct |
11 |
Correct |
1 ms |
336 KB |
Output is correct |
12 |
Correct |
1 ms |
336 KB |
Output is correct |
13 |
Correct |
1 ms |
336 KB |
Output is correct |
14 |
Correct |
1 ms |
464 KB |
Output is correct |
15 |
Correct |
1 ms |
464 KB |
Output is correct |
16 |
Correct |
1 ms |
464 KB |
Output is correct |
17 |
Correct |
1 ms |
464 KB |
Output is correct |
18 |
Correct |
1 ms |
632 KB |
Output is correct |
19 |
Correct |
1 ms |
592 KB |
Output is correct |
20 |
Correct |
1 ms |
464 KB |
Output is correct |
21 |
Correct |
1 ms |
464 KB |
Output is correct |
22 |
Correct |
1 ms |
464 KB |
Output is correct |
23 |
Correct |
1 ms |
336 KB |
Output is correct |
24 |
Correct |
1 ms |
464 KB |
Output is correct |
25 |
Correct |
1 ms |
464 KB |
Output is correct |
26 |
Correct |
1 ms |
464 KB |
Output is correct |
27 |
Correct |
1 ms |
464 KB |
Output is correct |
28 |
Correct |
1 ms |
464 KB |
Output is correct |
29 |
Correct |
1 ms |
336 KB |
Output is correct |
30 |
Correct |
1 ms |
336 KB |
Output is correct |
31 |
Correct |
1 ms |
464 KB |
Output is correct |
32 |
Correct |
1 ms |
464 KB |
Output is correct |
33 |
Correct |
1 ms |
464 KB |
Output is correct |
34 |
Correct |
2 ms |
464 KB |
Output is correct |
35 |
Correct |
1 ms |
336 KB |
Output is correct |
36 |
Correct |
2 ms |
592 KB |
Output is correct |
37 |
Correct |
1 ms |
592 KB |
Output is correct |
38 |
Correct |
1 ms |
592 KB |
Output is correct |
39 |
Correct |
1 ms |
464 KB |
Output is correct |
40 |
Correct |
1 ms |
464 KB |
Output is correct |
41 |
Correct |
1 ms |
464 KB |
Output is correct |
42 |
Correct |
1 ms |
336 KB |
Output is correct |
43 |
Correct |
344 ms |
5164 KB |
Output is correct |
44 |
Correct |
639 ms |
10060 KB |
Output is correct |
45 |
Correct |
575 ms |
10056 KB |
Output is correct |
46 |
Correct |
604 ms |
9652 KB |
Output is correct |
47 |
Correct |
570 ms |
5192 KB |
Output is correct |
48 |
Correct |
654 ms |
10056 KB |
Output is correct |
49 |
Correct |
619 ms |
10032 KB |
Output is correct |
50 |
Correct |
668 ms |
9996 KB |
Output is correct |
51 |
Correct |
305 ms |
592 KB |
Output is correct |
52 |
Correct |
582 ms |
976 KB |
Output is correct |
53 |
Correct |
596 ms |
976 KB |
Output is correct |
54 |
Correct |
610 ms |
976 KB |
Output is correct |
55 |
Correct |
617 ms |
14780 KB |
Output is correct |
56 |
Correct |
709 ms |
15124 KB |
Output is correct |
57 |
Correct |
694 ms |
15128 KB |
Output is correct |
58 |
Correct |
498 ms |
15024 KB |
Output is correct |
59 |
Correct |
788 ms |
29244 KB |
Output is correct |
60 |
Correct |
650 ms |
29164 KB |
Output is correct |
61 |
Correct |
500 ms |
720 KB |
Output is correct |
62 |
Correct |
551 ms |
804 KB |
Output is correct |
63 |
Correct |
622 ms |
844 KB |
Output is correct |
64 |
Correct |
631 ms |
1104 KB |
Output is correct |
65 |
Correct |
593 ms |
1104 KB |
Output is correct |
66 |
Correct |
612 ms |
976 KB |
Output is correct |
67 |
Correct |
668 ms |
1104 KB |
Output is correct |
68 |
Correct |
578 ms |
1104 KB |
Output is correct |
69 |
Correct |
526 ms |
720 KB |
Output is correct |
70 |
Correct |
656 ms |
720 KB |
Output is correct |
71 |
Correct |
530 ms |
1360 KB |
Output is correct |
72 |
Correct |
589 ms |
1104 KB |
Output is correct |
73 |
Correct |
652 ms |
848 KB |
Output is correct |
74 |
Correct |
586 ms |
848 KB |
Output is correct |
75 |
Correct |
516 ms |
720 KB |
Output is correct |
76 |
Correct |
585 ms |
1744 KB |
Output is correct |
77 |
Correct |
599 ms |
1744 KB |
Output is correct |
78 |
Correct |
552 ms |
1872 KB |
Output is correct |
79 |
Correct |
541 ms |
976 KB |
Output is correct |
80 |
Correct |
561 ms |
792 KB |
Output is correct |
81 |
Correct |
663 ms |
740 KB |
Output is correct |
82 |
Correct |
544 ms |
720 KB |
Output is correct |
83 |
Correct |
313 ms |
592 KB |
Output is correct |
84 |
Correct |
661 ms |
976 KB |
Output is correct |
85 |
Correct |
616 ms |
976 KB |
Output is correct |
86 |
Correct |
644 ms |
976 KB |
Output is correct |
87 |
Correct |
0 ms |
336 KB |
Output is correct |
88 |
Correct |
417 ms |
13372 KB |
Output is correct |
89 |
Correct |
698 ms |
9692 KB |
Output is correct |
90 |
Correct |
607 ms |
9460 KB |
Output is correct |
91 |
Correct |
723 ms |
15156 KB |
Output is correct |
92 |
Correct |
720 ms |
15188 KB |
Output is correct |
93 |
Correct |
744 ms |
14720 KB |
Output is correct |
94 |
Correct |
633 ms |
15232 KB |
Output is correct |
95 |
Correct |
711 ms |
15168 KB |
Output is correct |
96 |
Correct |
632 ms |
8488 KB |
Output is correct |
97 |
Correct |
697 ms |
8504 KB |
Output is correct |
98 |
Correct |
583 ms |
21436 KB |
Output is correct |
99 |
Correct |
831 ms |
15128 KB |
Output is correct |
100 |
Correct |
664 ms |
11560 KB |
Output is correct |
101 |
Correct |
653 ms |
10324 KB |
Output is correct |
102 |
Correct |
649 ms |
8472 KB |
Output is correct |
103 |
Correct |
684 ms |
29096 KB |
Output is correct |
104 |
Correct |
628 ms |
29500 KB |
Output is correct |
105 |
Correct |
665 ms |
29592 KB |
Output is correct |
106 |
Correct |
666 ms |
12028 KB |
Output is correct |
107 |
Correct |
631 ms |
8356 KB |
Output is correct |
108 |
Correct |
712 ms |
8532 KB |
Output is correct |
109 |
Correct |
720 ms |
8636 KB |
Output is correct |