#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "circuit.h"
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)
vector<ll> edges[200001];
ll possible[200001];
ll contrib[200001];
ll dps[200001];
vector<int> p;
int initdfs(ll a){
if (edges[a].size() == 0) return possible[a] = 1;
ll temp = 1;
for (auto&i : edges[a]){
temp *= initdfs(i);
temp %= 1000002022;
}
temp *= edges[a].size();
temp %= 1000002022;
return possible[a] = temp;
}
int dp(ll a){
if (a==0) return 1;
if (dps[a] != -1) return dps[a];
ll temp = 1;
for (auto&i : edges[p[a]]){
if (i != a) temp *= possible[i];
temp %= 1000002022;
}
dps[a] = temp * dp(p[a]) % 1000002022;
return dps[a];
}
ll n,m;
const ll NN = (1<<18);
ll tree[NN*2];
ll actual[NN*2];
ll lazy[NN*2];
int actupd(ll a, ll b, ll val, ll k=1, ll x = 0, ll y = NN-1){
if (b<x || a>y) return actual[k];
if (a<=x && y<=b){
actual[k] += val;
actual[k] %= 1000002022;
return actual[k];
}
ll mid = (x+y)/2;
actual[k] = actupd(a,b,val,k*2, x, mid) + actupd(a,b,val,k*2+1, mid+1, y);
actual[k] %= 1000002022;
return actual[k];
}
void prop(ll k){
lazy[k*2] += lazy[k];
lazy[k*2+1] += lazy[k];
if (lazy[k] %2==1){
tree[k] = (actual[k] - tree[k]+1000002022)%1000002022;
}
lazy[k] = 0;
}
int upd(ll a, ll b, ll k=1, ll x = 0, ll y = NN-1){
if (b<x || a>y) return lazy[k]%2==0 ? tree[k] : ((actual[k] - tree[k]+1000002022)%1000002022);
if (a<=x && y<=b){
lazy[k] += 1;
return lazy[k]%2==0 ? tree[k] : ((actual[k] - tree[k]+1000002022)%1000002022);
}
ll mid = (x+y)/2;
prop(k);
tree[k] = upd(a,b,k*2, x, mid) + upd(a,b,k*2+1, mid+1, y);
tree[k] %= 1000002022;
return lazy[k]%2==0 ? tree[k] : ((actual[k] - tree[k]+1000002022)%1000002022);
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
FOR(i,0,200001) dps[i] = -1;
FOR(i,0,NN*2) tree[i] = 0, actual[i] = 0, lazy[i] = 0;
p = P;
n = N;
m = M;
FOR(i,1,N+M){
edges[P[i]].push_back(i);
}
initdfs(0);
FOR(i,N,N+M){
ll temp = possible[i];
temp *= dp(i);
contrib[i] = temp%1000002022;
}
FOR(i,n,n+m){
actupd(i-n+1, i-n+1, contrib[i]);
}
FOR(i,0,NN*2) tree[i] = actual[i];
FOR(i,n,n+m){
if (A[i-n] == 0){
upd(i-n+1, i-n+1);
}
}
}
int count_ways(int L, int R) {
upd(L-n+1, R-n+1);
return lazy[1]%2==0 ? tree[1] : ((actual[1] - tree[1]+1000002022)%1000002022);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
18768 KB |
Output is correct |
2 |
Correct |
9 ms |
18768 KB |
Output is correct |
3 |
Correct |
13 ms |
18896 KB |
Output is correct |
4 |
Correct |
13 ms |
18896 KB |
Output is correct |
5 |
Correct |
13 ms |
18896 KB |
Output is correct |
6 |
Correct |
13 ms |
18896 KB |
Output is correct |
7 |
Correct |
13 ms |
18820 KB |
Output is correct |
8 |
Correct |
13 ms |
18896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
18828 KB |
Output is correct |
2 |
Correct |
9 ms |
18896 KB |
Output is correct |
3 |
Correct |
11 ms |
18896 KB |
Output is correct |
4 |
Correct |
9 ms |
18896 KB |
Output is correct |
5 |
Correct |
9 ms |
18896 KB |
Output is correct |
6 |
Correct |
12 ms |
18896 KB |
Output is correct |
7 |
Correct |
10 ms |
18888 KB |
Output is correct |
8 |
Correct |
10 ms |
18896 KB |
Output is correct |
9 |
Correct |
9 ms |
18896 KB |
Output is correct |
10 |
Correct |
9 ms |
18896 KB |
Output is correct |
11 |
Correct |
8 ms |
18896 KB |
Output is correct |
12 |
Correct |
9 ms |
18896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
18768 KB |
Output is correct |
2 |
Correct |
9 ms |
18768 KB |
Output is correct |
3 |
Correct |
13 ms |
18896 KB |
Output is correct |
4 |
Correct |
13 ms |
18896 KB |
Output is correct |
5 |
Correct |
13 ms |
18896 KB |
Output is correct |
6 |
Correct |
13 ms |
18896 KB |
Output is correct |
7 |
Correct |
13 ms |
18820 KB |
Output is correct |
8 |
Correct |
13 ms |
18896 KB |
Output is correct |
9 |
Correct |
9 ms |
18828 KB |
Output is correct |
10 |
Correct |
9 ms |
18896 KB |
Output is correct |
11 |
Correct |
11 ms |
18896 KB |
Output is correct |
12 |
Correct |
9 ms |
18896 KB |
Output is correct |
13 |
Correct |
9 ms |
18896 KB |
Output is correct |
14 |
Correct |
12 ms |
18896 KB |
Output is correct |
15 |
Correct |
10 ms |
18888 KB |
Output is correct |
16 |
Correct |
10 ms |
18896 KB |
Output is correct |
17 |
Correct |
9 ms |
18896 KB |
Output is correct |
18 |
Correct |
9 ms |
18896 KB |
Output is correct |
19 |
Correct |
8 ms |
18896 KB |
Output is correct |
20 |
Correct |
9 ms |
18896 KB |
Output is correct |
21 |
Correct |
10 ms |
18896 KB |
Output is correct |
22 |
Correct |
9 ms |
18896 KB |
Output is correct |
23 |
Correct |
9 ms |
18896 KB |
Output is correct |
24 |
Correct |
10 ms |
18896 KB |
Output is correct |
25 |
Correct |
10 ms |
18896 KB |
Output is correct |
26 |
Correct |
10 ms |
18896 KB |
Output is correct |
27 |
Correct |
9 ms |
18896 KB |
Output is correct |
28 |
Correct |
9 ms |
18892 KB |
Output is correct |
29 |
Correct |
13 ms |
18896 KB |
Output is correct |
30 |
Correct |
13 ms |
18896 KB |
Output is correct |
31 |
Correct |
9 ms |
18896 KB |
Output is correct |
32 |
Correct |
10 ms |
18896 KB |
Output is correct |
33 |
Correct |
11 ms |
19024 KB |
Output is correct |
34 |
Correct |
9 ms |
18896 KB |
Output is correct |
35 |
Correct |
10 ms |
18852 KB |
Output is correct |
36 |
Correct |
9 ms |
18896 KB |
Output is correct |
37 |
Correct |
13 ms |
19024 KB |
Output is correct |
38 |
Correct |
13 ms |
19024 KB |
Output is correct |
39 |
Correct |
9 ms |
18896 KB |
Output is correct |
40 |
Correct |
9 ms |
18896 KB |
Output is correct |
41 |
Correct |
9 ms |
18896 KB |
Output is correct |
42 |
Correct |
10 ms |
18896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
557 ms |
21828 KB |
Output is correct |
2 |
Correct |
641 ms |
24520 KB |
Output is correct |
3 |
Correct |
728 ms |
24448 KB |
Output is correct |
4 |
Correct |
712 ms |
24528 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
557 ms |
21828 KB |
Output is correct |
2 |
Correct |
641 ms |
24520 KB |
Output is correct |
3 |
Correct |
728 ms |
24448 KB |
Output is correct |
4 |
Correct |
712 ms |
24528 KB |
Output is correct |
5 |
Correct |
472 ms |
21740 KB |
Output is correct |
6 |
Correct |
813 ms |
24520 KB |
Output is correct |
7 |
Correct |
864 ms |
24472 KB |
Output is correct |
8 |
Correct |
565 ms |
24484 KB |
Output is correct |
9 |
Correct |
357 ms |
19152 KB |
Output is correct |
10 |
Correct |
742 ms |
19152 KB |
Output is correct |
11 |
Correct |
686 ms |
19152 KB |
Output is correct |
12 |
Correct |
663 ms |
19152 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
18828 KB |
Output is correct |
2 |
Correct |
9 ms |
18896 KB |
Output is correct |
3 |
Correct |
11 ms |
18896 KB |
Output is correct |
4 |
Correct |
9 ms |
18896 KB |
Output is correct |
5 |
Correct |
9 ms |
18896 KB |
Output is correct |
6 |
Correct |
12 ms |
18896 KB |
Output is correct |
7 |
Correct |
10 ms |
18888 KB |
Output is correct |
8 |
Correct |
10 ms |
18896 KB |
Output is correct |
9 |
Correct |
9 ms |
18896 KB |
Output is correct |
10 |
Correct |
9 ms |
18896 KB |
Output is correct |
11 |
Correct |
8 ms |
18896 KB |
Output is correct |
12 |
Correct |
9 ms |
18896 KB |
Output is correct |
13 |
Correct |
557 ms |
21828 KB |
Output is correct |
14 |
Correct |
641 ms |
24520 KB |
Output is correct |
15 |
Correct |
728 ms |
24448 KB |
Output is correct |
16 |
Correct |
712 ms |
24528 KB |
Output is correct |
17 |
Correct |
472 ms |
21740 KB |
Output is correct |
18 |
Correct |
813 ms |
24520 KB |
Output is correct |
19 |
Correct |
864 ms |
24472 KB |
Output is correct |
20 |
Correct |
565 ms |
24484 KB |
Output is correct |
21 |
Correct |
357 ms |
19152 KB |
Output is correct |
22 |
Correct |
742 ms |
19152 KB |
Output is correct |
23 |
Correct |
686 ms |
19152 KB |
Output is correct |
24 |
Correct |
663 ms |
19152 KB |
Output is correct |
25 |
Correct |
848 ms |
27336 KB |
Output is correct |
26 |
Correct |
842 ms |
27420 KB |
Output is correct |
27 |
Correct |
731 ms |
27480 KB |
Output is correct |
28 |
Correct |
616 ms |
27484 KB |
Output is correct |
29 |
Correct |
867 ms |
31036 KB |
Output is correct |
30 |
Correct |
745 ms |
31132 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
18768 KB |
Output is correct |
2 |
Correct |
9 ms |
18768 KB |
Output is correct |
3 |
Correct |
13 ms |
18896 KB |
Output is correct |
4 |
Correct |
13 ms |
18896 KB |
Output is correct |
5 |
Correct |
13 ms |
18896 KB |
Output is correct |
6 |
Correct |
13 ms |
18896 KB |
Output is correct |
7 |
Correct |
13 ms |
18820 KB |
Output is correct |
8 |
Correct |
13 ms |
18896 KB |
Output is correct |
9 |
Correct |
9 ms |
18828 KB |
Output is correct |
10 |
Correct |
9 ms |
18896 KB |
Output is correct |
11 |
Correct |
11 ms |
18896 KB |
Output is correct |
12 |
Correct |
9 ms |
18896 KB |
Output is correct |
13 |
Correct |
9 ms |
18896 KB |
Output is correct |
14 |
Correct |
12 ms |
18896 KB |
Output is correct |
15 |
Correct |
10 ms |
18888 KB |
Output is correct |
16 |
Correct |
10 ms |
18896 KB |
Output is correct |
17 |
Correct |
9 ms |
18896 KB |
Output is correct |
18 |
Correct |
9 ms |
18896 KB |
Output is correct |
19 |
Correct |
8 ms |
18896 KB |
Output is correct |
20 |
Correct |
9 ms |
18896 KB |
Output is correct |
21 |
Correct |
10 ms |
18896 KB |
Output is correct |
22 |
Correct |
9 ms |
18896 KB |
Output is correct |
23 |
Correct |
9 ms |
18896 KB |
Output is correct |
24 |
Correct |
10 ms |
18896 KB |
Output is correct |
25 |
Correct |
10 ms |
18896 KB |
Output is correct |
26 |
Correct |
10 ms |
18896 KB |
Output is correct |
27 |
Correct |
9 ms |
18896 KB |
Output is correct |
28 |
Correct |
9 ms |
18892 KB |
Output is correct |
29 |
Correct |
13 ms |
18896 KB |
Output is correct |
30 |
Correct |
13 ms |
18896 KB |
Output is correct |
31 |
Correct |
9 ms |
18896 KB |
Output is correct |
32 |
Correct |
10 ms |
18896 KB |
Output is correct |
33 |
Correct |
11 ms |
19024 KB |
Output is correct |
34 |
Correct |
9 ms |
18896 KB |
Output is correct |
35 |
Correct |
10 ms |
18852 KB |
Output is correct |
36 |
Correct |
9 ms |
18896 KB |
Output is correct |
37 |
Correct |
13 ms |
19024 KB |
Output is correct |
38 |
Correct |
13 ms |
19024 KB |
Output is correct |
39 |
Correct |
9 ms |
18896 KB |
Output is correct |
40 |
Correct |
9 ms |
18896 KB |
Output is correct |
41 |
Correct |
9 ms |
18896 KB |
Output is correct |
42 |
Correct |
10 ms |
18896 KB |
Output is correct |
43 |
Correct |
521 ms |
19152 KB |
Output is correct |
44 |
Correct |
616 ms |
19152 KB |
Output is correct |
45 |
Correct |
813 ms |
19152 KB |
Output is correct |
46 |
Correct |
708 ms |
19280 KB |
Output is correct |
47 |
Correct |
648 ms |
19280 KB |
Output is correct |
48 |
Correct |
764 ms |
19352 KB |
Output is correct |
49 |
Correct |
698 ms |
19280 KB |
Output is correct |
50 |
Correct |
741 ms |
19280 KB |
Output is correct |
51 |
Correct |
794 ms |
19244 KB |
Output is correct |
52 |
Correct |
862 ms |
19272 KB |
Output is correct |
53 |
Correct |
661 ms |
19280 KB |
Output is correct |
54 |
Correct |
682 ms |
19280 KB |
Output is correct |
55 |
Correct |
714 ms |
19152 KB |
Output is correct |
56 |
Correct |
599 ms |
19152 KB |
Output is correct |
57 |
Correct |
633 ms |
19024 KB |
Output is correct |
58 |
Correct |
705 ms |
19456 KB |
Output is correct |
59 |
Correct |
792 ms |
19588 KB |
Output is correct |
60 |
Correct |
771 ms |
19592 KB |
Output is correct |
61 |
Correct |
682 ms |
19152 KB |
Output is correct |
62 |
Correct |
724 ms |
19024 KB |
Output is correct |
63 |
Correct |
666 ms |
19072 KB |
Output is correct |
64 |
Correct |
605 ms |
19024 KB |
Output is correct |
65 |
Correct |
427 ms |
19024 KB |
Output is correct |
66 |
Correct |
628 ms |
19152 KB |
Output is correct |
67 |
Correct |
744 ms |
19208 KB |
Output is correct |
68 |
Correct |
605 ms |
19108 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
18768 KB |
Output is correct |
2 |
Correct |
9 ms |
18768 KB |
Output is correct |
3 |
Correct |
13 ms |
18896 KB |
Output is correct |
4 |
Correct |
13 ms |
18896 KB |
Output is correct |
5 |
Correct |
13 ms |
18896 KB |
Output is correct |
6 |
Correct |
13 ms |
18896 KB |
Output is correct |
7 |
Correct |
13 ms |
18820 KB |
Output is correct |
8 |
Correct |
13 ms |
18896 KB |
Output is correct |
9 |
Correct |
9 ms |
18828 KB |
Output is correct |
10 |
Correct |
9 ms |
18896 KB |
Output is correct |
11 |
Correct |
11 ms |
18896 KB |
Output is correct |
12 |
Correct |
9 ms |
18896 KB |
Output is correct |
13 |
Correct |
9 ms |
18896 KB |
Output is correct |
14 |
Correct |
12 ms |
18896 KB |
Output is correct |
15 |
Correct |
10 ms |
18888 KB |
Output is correct |
16 |
Correct |
10 ms |
18896 KB |
Output is correct |
17 |
Correct |
9 ms |
18896 KB |
Output is correct |
18 |
Correct |
9 ms |
18896 KB |
Output is correct |
19 |
Correct |
8 ms |
18896 KB |
Output is correct |
20 |
Correct |
9 ms |
18896 KB |
Output is correct |
21 |
Correct |
10 ms |
18896 KB |
Output is correct |
22 |
Correct |
9 ms |
18896 KB |
Output is correct |
23 |
Correct |
9 ms |
18896 KB |
Output is correct |
24 |
Correct |
10 ms |
18896 KB |
Output is correct |
25 |
Correct |
10 ms |
18896 KB |
Output is correct |
26 |
Correct |
10 ms |
18896 KB |
Output is correct |
27 |
Correct |
9 ms |
18896 KB |
Output is correct |
28 |
Correct |
9 ms |
18892 KB |
Output is correct |
29 |
Correct |
13 ms |
18896 KB |
Output is correct |
30 |
Correct |
13 ms |
18896 KB |
Output is correct |
31 |
Correct |
9 ms |
18896 KB |
Output is correct |
32 |
Correct |
10 ms |
18896 KB |
Output is correct |
33 |
Correct |
11 ms |
19024 KB |
Output is correct |
34 |
Correct |
9 ms |
18896 KB |
Output is correct |
35 |
Correct |
10 ms |
18852 KB |
Output is correct |
36 |
Correct |
9 ms |
18896 KB |
Output is correct |
37 |
Correct |
13 ms |
19024 KB |
Output is correct |
38 |
Correct |
13 ms |
19024 KB |
Output is correct |
39 |
Correct |
9 ms |
18896 KB |
Output is correct |
40 |
Correct |
9 ms |
18896 KB |
Output is correct |
41 |
Correct |
9 ms |
18896 KB |
Output is correct |
42 |
Correct |
10 ms |
18896 KB |
Output is correct |
43 |
Correct |
557 ms |
21828 KB |
Output is correct |
44 |
Correct |
641 ms |
24520 KB |
Output is correct |
45 |
Correct |
728 ms |
24448 KB |
Output is correct |
46 |
Correct |
712 ms |
24528 KB |
Output is correct |
47 |
Correct |
472 ms |
21740 KB |
Output is correct |
48 |
Correct |
813 ms |
24520 KB |
Output is correct |
49 |
Correct |
864 ms |
24472 KB |
Output is correct |
50 |
Correct |
565 ms |
24484 KB |
Output is correct |
51 |
Correct |
357 ms |
19152 KB |
Output is correct |
52 |
Correct |
742 ms |
19152 KB |
Output is correct |
53 |
Correct |
686 ms |
19152 KB |
Output is correct |
54 |
Correct |
663 ms |
19152 KB |
Output is correct |
55 |
Correct |
848 ms |
27336 KB |
Output is correct |
56 |
Correct |
842 ms |
27420 KB |
Output is correct |
57 |
Correct |
731 ms |
27480 KB |
Output is correct |
58 |
Correct |
616 ms |
27484 KB |
Output is correct |
59 |
Correct |
867 ms |
31036 KB |
Output is correct |
60 |
Correct |
745 ms |
31132 KB |
Output is correct |
61 |
Correct |
521 ms |
19152 KB |
Output is correct |
62 |
Correct |
616 ms |
19152 KB |
Output is correct |
63 |
Correct |
813 ms |
19152 KB |
Output is correct |
64 |
Correct |
708 ms |
19280 KB |
Output is correct |
65 |
Correct |
648 ms |
19280 KB |
Output is correct |
66 |
Correct |
764 ms |
19352 KB |
Output is correct |
67 |
Correct |
698 ms |
19280 KB |
Output is correct |
68 |
Correct |
741 ms |
19280 KB |
Output is correct |
69 |
Correct |
794 ms |
19244 KB |
Output is correct |
70 |
Correct |
862 ms |
19272 KB |
Output is correct |
71 |
Correct |
661 ms |
19280 KB |
Output is correct |
72 |
Correct |
682 ms |
19280 KB |
Output is correct |
73 |
Correct |
714 ms |
19152 KB |
Output is correct |
74 |
Correct |
599 ms |
19152 KB |
Output is correct |
75 |
Correct |
633 ms |
19024 KB |
Output is correct |
76 |
Correct |
705 ms |
19456 KB |
Output is correct |
77 |
Correct |
792 ms |
19588 KB |
Output is correct |
78 |
Correct |
771 ms |
19592 KB |
Output is correct |
79 |
Correct |
682 ms |
19152 KB |
Output is correct |
80 |
Correct |
724 ms |
19024 KB |
Output is correct |
81 |
Correct |
666 ms |
19072 KB |
Output is correct |
82 |
Correct |
605 ms |
19024 KB |
Output is correct |
83 |
Correct |
427 ms |
19024 KB |
Output is correct |
84 |
Correct |
628 ms |
19152 KB |
Output is correct |
85 |
Correct |
744 ms |
19208 KB |
Output is correct |
86 |
Correct |
605 ms |
19108 KB |
Output is correct |
87 |
Correct |
7 ms |
18768 KB |
Output is correct |
88 |
Correct |
539 ms |
27032 KB |
Output is correct |
89 |
Correct |
909 ms |
24616 KB |
Output is correct |
90 |
Correct |
804 ms |
24648 KB |
Output is correct |
91 |
Correct |
830 ms |
28100 KB |
Output is correct |
92 |
Correct |
735 ms |
28192 KB |
Output is correct |
93 |
Correct |
931 ms |
28024 KB |
Output is correct |
94 |
Correct |
816 ms |
28016 KB |
Output is correct |
95 |
Correct |
656 ms |
27976 KB |
Output is correct |
96 |
Execution timed out |
3051 ms |
22664 KB |
Time limit exceeded |
97 |
Halted |
0 ms |
0 KB |
- |