#include "circuit.h"
// #pragma GCC optimize("trapv")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define loop(x, i) for (int i = 0; i < x; i++)
#define rev(x, i) for (int i = (int)x - 1; i >= 0; i--)
#define ALL(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef signed i32;
typedef array<int, 2> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<i32> vi32;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
constexpr int MOD = 1'000'002'022;
vvi children;
vi term01;
int n, m, treeN = 1;
vi vs;
struct val
{
int v = 0, totalV = 0;
void swap()
{
v = (totalV - v + MOD) % MOD;
}
val operator+(const val &b)
{
val a = *this, res;
res.v = a.v + b.v;
res.totalV = a.totalV + b.totalV;
res.totalV %= MOD;
res.v %= MOD;
return res;
}
};
vector<val> tree;
vb lazy;
void pull(int i)
{
tree[i] = tree[2 * i] + tree[2 * i + 1];
}
void push(int i)
{
if (!lazy[i])
return;
tree[i].swap();
if (i < treeN)
{
lazy[2 * i].flip();
lazy[2 * i + 1].flip();
}
lazy[i] = 0;
}
val operation(int i, int l, int r, int ql, int qr, int op)
{
push(i);
if (r < ql || qr < l)
return {};
if (ql <= l && r <= qr)
{
if (op == 1)
{
lazy[i] = 1;
push(i);
}
return tree[i];
}
int mid = (l + r) / 2;
val res = operation(2 * i, l, mid, ql, qr, op) +
operation(2 * i + 1, mid + 1, r, ql, qr, op);
pull(i);
return res;
};
int calc01s(int i)
{
if (i >= n)
{
return term01[i] = 1;
}
int all = sz(children[i]);
for (int j : children[i])
{
int v = calc01s(j);
all *= v;
all %= MOD;
}
return term01[i] = all;
}
vi calc(int i)
{
if (i >= n)
{
vs[i - n] = 1;
return {i - n};
}
int c = sz(children[i]);
vi prod, prefProd(c + 1, 1), sufProd(c + 1, 1);
vvi leafs;
for (int j : children[i])
{
leafs.pb(move(calc(j)));
prod.pb(term01[j]);
}
loop(c, j)
{
prefProd[j + 1] = prefProd[j] * prod[j];
prefProd[j + 1] %= MOD;
}
rev(c, j)
{
sufProd[j] = sufProd[j + 1] * prod[j];
sufProd[j] %= MOD;
}
vi res;
loop(c, j)
{
int mult = (prefProd[j] * sufProd[j + 1]) % MOD;
for (int ix : leafs[j])
{
vs[ix] = (vs[ix] * mult) % MOD;
res.pb(ix);
}
}
return res;
// return move(res);
}
void init(i32 N, i32 M, vi32 P, vi32 A)
{
n = N;
m = M;
while (treeN < m)
treeN *= 2;
tree.resize(2 * treeN);
lazy.resize(2 * treeN);
children = vvi(N);
term01 = vi(N + M);
vs = vi(M);
loop(sz(P), i)
{
if (i == 0)
continue;
children[P[i]].pb(i);
}
calc01s(0);
calc(0);
loop(m, i)
{
tree[treeN + i].totalV = vs[i];
if (A[i])
tree[treeN + i].v = vs[i];
}
rev(treeN, i) pull(i);
}
i32 count_ways(i32 L, i32 R)
{
operation(1, 0, treeN - 1, L - n, R - n, 1);
return (i32)operation(1, 0, treeN - 1, 0, m - 1, 0).v;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
600 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
600 KB |
Output is correct |
8 |
Correct |
1 ms |
600 KB |
Output is correct |
9 |
Correct |
1 ms |
356 KB |
Output is correct |
10 |
Correct |
2 ms |
856 KB |
Output is correct |
11 |
Correct |
5 ms |
856 KB |
Output is correct |
12 |
Correct |
2 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
600 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
600 KB |
Output is correct |
16 |
Correct |
1 ms |
600 KB |
Output is correct |
17 |
Correct |
1 ms |
356 KB |
Output is correct |
18 |
Correct |
2 ms |
856 KB |
Output is correct |
19 |
Correct |
5 ms |
856 KB |
Output is correct |
20 |
Correct |
2 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
600 KB |
Output is correct |
25 |
Correct |
2 ms |
600 KB |
Output is correct |
26 |
Correct |
2 ms |
600 KB |
Output is correct |
27 |
Correct |
2 ms |
604 KB |
Output is correct |
28 |
Correct |
1 ms |
600 KB |
Output is correct |
29 |
Correct |
1 ms |
344 KB |
Output is correct |
30 |
Correct |
0 ms |
344 KB |
Output is correct |
31 |
Correct |
1 ms |
608 KB |
Output is correct |
32 |
Correct |
1 ms |
608 KB |
Output is correct |
33 |
Correct |
1 ms |
352 KB |
Output is correct |
34 |
Correct |
1 ms |
352 KB |
Output is correct |
35 |
Correct |
1 ms |
356 KB |
Output is correct |
36 |
Correct |
4 ms |
860 KB |
Output is correct |
37 |
Correct |
3 ms |
1004 KB |
Output is correct |
38 |
Correct |
5 ms |
864 KB |
Output is correct |
39 |
Correct |
1 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
41 |
Correct |
1 ms |
344 KB |
Output is correct |
42 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
483 ms |
5460 KB |
Output is correct |
2 |
Correct |
698 ms |
10360 KB |
Output is correct |
3 |
Correct |
723 ms |
10256 KB |
Output is correct |
4 |
Correct |
708 ms |
10256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
483 ms |
5460 KB |
Output is correct |
2 |
Correct |
698 ms |
10360 KB |
Output is correct |
3 |
Correct |
723 ms |
10256 KB |
Output is correct |
4 |
Correct |
708 ms |
10256 KB |
Output is correct |
5 |
Correct |
587 ms |
5456 KB |
Output is correct |
6 |
Correct |
844 ms |
10196 KB |
Output is correct |
7 |
Correct |
782 ms |
10244 KB |
Output is correct |
8 |
Correct |
717 ms |
10360 KB |
Output is correct |
9 |
Correct |
319 ms |
600 KB |
Output is correct |
10 |
Correct |
646 ms |
856 KB |
Output is correct |
11 |
Correct |
660 ms |
856 KB |
Output is correct |
12 |
Correct |
695 ms |
856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
1 ms |
344 KB |
Output is correct |
3 |
Correct |
1 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
1 ms |
600 KB |
Output is correct |
8 |
Correct |
1 ms |
600 KB |
Output is correct |
9 |
Correct |
1 ms |
356 KB |
Output is correct |
10 |
Correct |
2 ms |
856 KB |
Output is correct |
11 |
Correct |
5 ms |
856 KB |
Output is correct |
12 |
Correct |
2 ms |
344 KB |
Output is correct |
13 |
Correct |
483 ms |
5460 KB |
Output is correct |
14 |
Correct |
698 ms |
10360 KB |
Output is correct |
15 |
Correct |
723 ms |
10256 KB |
Output is correct |
16 |
Correct |
708 ms |
10256 KB |
Output is correct |
17 |
Correct |
587 ms |
5456 KB |
Output is correct |
18 |
Correct |
844 ms |
10196 KB |
Output is correct |
19 |
Correct |
782 ms |
10244 KB |
Output is correct |
20 |
Correct |
717 ms |
10360 KB |
Output is correct |
21 |
Correct |
319 ms |
600 KB |
Output is correct |
22 |
Correct |
646 ms |
856 KB |
Output is correct |
23 |
Correct |
660 ms |
856 KB |
Output is correct |
24 |
Correct |
695 ms |
856 KB |
Output is correct |
25 |
Correct |
810 ms |
17192 KB |
Output is correct |
26 |
Correct |
832 ms |
17232 KB |
Output is correct |
27 |
Correct |
830 ms |
17440 KB |
Output is correct |
28 |
Correct |
620 ms |
17264 KB |
Output is correct |
29 |
Execution timed out |
3012 ms |
47440 KB |
Time limit exceeded |
30 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
600 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
600 KB |
Output is correct |
16 |
Correct |
1 ms |
600 KB |
Output is correct |
17 |
Correct |
1 ms |
356 KB |
Output is correct |
18 |
Correct |
2 ms |
856 KB |
Output is correct |
19 |
Correct |
5 ms |
856 KB |
Output is correct |
20 |
Correct |
2 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
600 KB |
Output is correct |
25 |
Correct |
2 ms |
600 KB |
Output is correct |
26 |
Correct |
2 ms |
600 KB |
Output is correct |
27 |
Correct |
2 ms |
604 KB |
Output is correct |
28 |
Correct |
1 ms |
600 KB |
Output is correct |
29 |
Correct |
1 ms |
344 KB |
Output is correct |
30 |
Correct |
0 ms |
344 KB |
Output is correct |
31 |
Correct |
1 ms |
608 KB |
Output is correct |
32 |
Correct |
1 ms |
608 KB |
Output is correct |
33 |
Correct |
1 ms |
352 KB |
Output is correct |
34 |
Correct |
1 ms |
352 KB |
Output is correct |
35 |
Correct |
1 ms |
356 KB |
Output is correct |
36 |
Correct |
4 ms |
860 KB |
Output is correct |
37 |
Correct |
3 ms |
1004 KB |
Output is correct |
38 |
Correct |
5 ms |
864 KB |
Output is correct |
39 |
Correct |
1 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
41 |
Correct |
1 ms |
344 KB |
Output is correct |
42 |
Correct |
1 ms |
348 KB |
Output is correct |
43 |
Correct |
512 ms |
856 KB |
Output is correct |
44 |
Correct |
666 ms |
856 KB |
Output is correct |
45 |
Correct |
688 ms |
856 KB |
Output is correct |
46 |
Correct |
628 ms |
1368 KB |
Output is correct |
47 |
Correct |
726 ms |
1368 KB |
Output is correct |
48 |
Correct |
726 ms |
1368 KB |
Output is correct |
49 |
Correct |
727 ms |
1368 KB |
Output is correct |
50 |
Correct |
721 ms |
1368 KB |
Output is correct |
51 |
Correct |
644 ms |
1368 KB |
Output is correct |
52 |
Correct |
717 ms |
1368 KB |
Output is correct |
53 |
Correct |
610 ms |
2392 KB |
Output is correct |
54 |
Correct |
750 ms |
1620 KB |
Output is correct |
55 |
Correct |
682 ms |
1112 KB |
Output is correct |
56 |
Correct |
706 ms |
1096 KB |
Output is correct |
57 |
Correct |
683 ms |
856 KB |
Output is correct |
58 |
Correct |
644 ms |
2648 KB |
Output is correct |
59 |
Correct |
788 ms |
3416 KB |
Output is correct |
60 |
Correct |
846 ms |
3416 KB |
Output is correct |
61 |
Correct |
668 ms |
1368 KB |
Output is correct |
62 |
Correct |
687 ms |
856 KB |
Output is correct |
63 |
Correct |
689 ms |
856 KB |
Output is correct |
64 |
Correct |
721 ms |
1112 KB |
Output is correct |
65 |
Correct |
324 ms |
600 KB |
Output is correct |
66 |
Correct |
661 ms |
856 KB |
Output is correct |
67 |
Correct |
632 ms |
856 KB |
Output is correct |
68 |
Correct |
699 ms |
856 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
344 KB |
Output is correct |
6 |
Correct |
1 ms |
344 KB |
Output is correct |
7 |
Correct |
0 ms |
600 KB |
Output is correct |
8 |
Correct |
1 ms |
344 KB |
Output is correct |
9 |
Correct |
0 ms |
344 KB |
Output is correct |
10 |
Correct |
1 ms |
344 KB |
Output is correct |
11 |
Correct |
1 ms |
344 KB |
Output is correct |
12 |
Correct |
1 ms |
344 KB |
Output is correct |
13 |
Correct |
1 ms |
344 KB |
Output is correct |
14 |
Correct |
1 ms |
344 KB |
Output is correct |
15 |
Correct |
1 ms |
600 KB |
Output is correct |
16 |
Correct |
1 ms |
600 KB |
Output is correct |
17 |
Correct |
1 ms |
356 KB |
Output is correct |
18 |
Correct |
2 ms |
856 KB |
Output is correct |
19 |
Correct |
5 ms |
856 KB |
Output is correct |
20 |
Correct |
2 ms |
344 KB |
Output is correct |
21 |
Correct |
1 ms |
344 KB |
Output is correct |
22 |
Correct |
1 ms |
344 KB |
Output is correct |
23 |
Correct |
1 ms |
344 KB |
Output is correct |
24 |
Correct |
1 ms |
600 KB |
Output is correct |
25 |
Correct |
2 ms |
600 KB |
Output is correct |
26 |
Correct |
2 ms |
600 KB |
Output is correct |
27 |
Correct |
2 ms |
604 KB |
Output is correct |
28 |
Correct |
1 ms |
600 KB |
Output is correct |
29 |
Correct |
1 ms |
344 KB |
Output is correct |
30 |
Correct |
0 ms |
344 KB |
Output is correct |
31 |
Correct |
1 ms |
608 KB |
Output is correct |
32 |
Correct |
1 ms |
608 KB |
Output is correct |
33 |
Correct |
1 ms |
352 KB |
Output is correct |
34 |
Correct |
1 ms |
352 KB |
Output is correct |
35 |
Correct |
1 ms |
356 KB |
Output is correct |
36 |
Correct |
4 ms |
860 KB |
Output is correct |
37 |
Correct |
3 ms |
1004 KB |
Output is correct |
38 |
Correct |
5 ms |
864 KB |
Output is correct |
39 |
Correct |
1 ms |
348 KB |
Output is correct |
40 |
Correct |
1 ms |
348 KB |
Output is correct |
41 |
Correct |
1 ms |
344 KB |
Output is correct |
42 |
Correct |
1 ms |
348 KB |
Output is correct |
43 |
Correct |
483 ms |
5460 KB |
Output is correct |
44 |
Correct |
698 ms |
10360 KB |
Output is correct |
45 |
Correct |
723 ms |
10256 KB |
Output is correct |
46 |
Correct |
708 ms |
10256 KB |
Output is correct |
47 |
Correct |
587 ms |
5456 KB |
Output is correct |
48 |
Correct |
844 ms |
10196 KB |
Output is correct |
49 |
Correct |
782 ms |
10244 KB |
Output is correct |
50 |
Correct |
717 ms |
10360 KB |
Output is correct |
51 |
Correct |
319 ms |
600 KB |
Output is correct |
52 |
Correct |
646 ms |
856 KB |
Output is correct |
53 |
Correct |
660 ms |
856 KB |
Output is correct |
54 |
Correct |
695 ms |
856 KB |
Output is correct |
55 |
Correct |
810 ms |
17192 KB |
Output is correct |
56 |
Correct |
832 ms |
17232 KB |
Output is correct |
57 |
Correct |
830 ms |
17440 KB |
Output is correct |
58 |
Correct |
620 ms |
17264 KB |
Output is correct |
59 |
Execution timed out |
3012 ms |
47440 KB |
Time limit exceeded |
60 |
Halted |
0 ms |
0 KB |
- |