#include <iostream>
#include <vector>
using i64 = int64_t;
const i64 MOD = 1'000'002'022;
struct Node {
i64 a1, a0, ax;
Node() : a1(0), a0(1), ax(1) {}
explicit Node(bool value) : a1(value), a0(!value), ax(1) {}
Node(i64 a1, i64 a0, i64 ax) : a1(a1), a0(a0), ax(ax) {}
void toggle() { std::swap(a1, a0); }
Node operator*(const Node &rhs) const {
return {(a1 * rhs.ax + ax * rhs.a1) % MOD,
(a0 * rhs.ax + ax * rhs.a0) % MOD, ax * rhs.ax * 2 % MOD};
}
};
struct SegmentTree {
std::vector<Node> values;
std::vector<bool> toggled;
i64 offset;
SegmentTree() : values{}, toggled{}, offset{0} {}
explicit SegmentTree(size_t sz)
: values(2 * sz), toggled(2 * sz, false), offset(sz) {}
void update(i64 idx, bool value) {
idx += offset;
values[idx] = Node(value);
while (idx /= 2) pull(idx);
}
void toggle_range(i64 l, i64 r) { toggle_range(l, r, 1, 0, offset); }
void toggle_range(i64 l, i64 r, i64 v, i64 s, i64 e) {
if (e <= l || r <= s) {
return;
} else if (l <= s && e <= r) {
values[v].toggle();
toggled[v] = !toggled[v];
} else {
i64 m = (s + e) / 2;
push(v);
toggle_range(l, r, 2 * v, s, m);
toggle_range(l, r, 2 * v + 1, m, e);
pull(v);
}
}
void push(i64 v) {
if (toggled[v]) {
toggled[v] = false;
toggled[2 * v] = !toggled[2 * v];
toggled[2 * v + 1] = !toggled[2 * v + 1];
values[2 * v].toggle();
values[2 * v + 1].toggle();
}
}
void pull(i64 v) { values[v] = values[2 * v] * values[2 * v + 1]; }
const Node &root() const { return values[1]; }
};
int n, m;
std::vector<int> p, a;
std::vector<std::vector<int>> children;
SegmentTree st;
bool is_45 = true;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N;
m = M;
p = P;
a = A;
children.resize(N);
for (i64 i = 1; i < N + M; i++) {
children[P[i]].push_back(i);
}
if (M == N + 1 && (M & (M - 1)) == 0) {
for (i64 i = 0; i < N; i++) {
if (children[i].size() != 2) {
is_45 = false;
break;
}
}
}
if (is_45) {
st = SegmentTree(N + 1);
for (i64 i = 0; i < M; i++) {
st.update(i, A[i]);
}
}
}
auto dfs(int node) -> std::pair<i64, i64> {
if (node >= n) {
return {a[node - n] ? 1 : 0, 1};
}
i64 cs = children[node].size();
std::vector<std::pair<i64, i64>> results;
results.reserve(1 + cs);
for (i64 c : children[node]) {
results.push_back(dfs(c));
}
std::vector<i64> xs_left{1}, xs_right{1};
xs_left.reserve(1 + cs);
xs_right.reserve(1 + cs);
for (i64 i = 0; i < cs; i++) {
xs_left.push_back(xs_left.back() * results[i].second % MOD);
xs_right.push_back(xs_right.back() * results[cs - i - 1].second % MOD);
}
i64 sum = 0, of = cs;
for (i64 i = 0; i < cs; i++) {
sum += results[i].first * xs_left[i] % MOD * xs_right[cs - i - 1];
of *= results[i].second;
sum %= MOD;
of %= MOD;
}
return {sum, of};
}
int count_ways(int l, int r) {
r += 1;
l -= n;
r -= n;
if (is_45) {
st.toggle_range(l, r);
return st.root().a1;
} else {
for (i64 i = l; i < r; i++) {
a[i] = !a[i];
}
return dfs(0).first;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
0 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '706880838', found: '771166560' |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
495 ms |
4772 KB |
Output is correct |
| 2 |
Correct |
621 ms |
9228 KB |
Output is correct |
| 3 |
Correct |
671 ms |
9264 KB |
Output is correct |
| 4 |
Correct |
683 ms |
9260 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
495 ms |
4772 KB |
Output is correct |
| 2 |
Correct |
621 ms |
9228 KB |
Output is correct |
| 3 |
Correct |
671 ms |
9264 KB |
Output is correct |
| 4 |
Correct |
683 ms |
9260 KB |
Output is correct |
| 5 |
Correct |
553 ms |
4816 KB |
Output is correct |
| 6 |
Correct |
728 ms |
9300 KB |
Output is correct |
| 7 |
Correct |
665 ms |
9252 KB |
Output is correct |
| 8 |
Correct |
654 ms |
9308 KB |
Output is correct |
| 9 |
Correct |
346 ms |
464 KB |
Output is correct |
| 10 |
Correct |
674 ms |
848 KB |
Output is correct |
| 11 |
Correct |
704 ms |
848 KB |
Output is correct |
| 12 |
Correct |
554 ms |
848 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Correct |
1 ms |
336 KB |
Output is correct |
| 4 |
Correct |
0 ms |
336 KB |
Output is correct |
| 5 |
Correct |
1 ms |
336 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
336 KB |
1st lines differ - on the 1st token, expected: '706880838', found: '771166560' |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
208 KB |
Output is correct |
| 2 |
Correct |
0 ms |
208 KB |
Output is correct |
| 3 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
