This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
using i64 = int64_t;
const i64 MOD = 1'000'002'022;
struct Node {
i64 a1, ax;
Node() : a1(0), ax(1) {}
explicit Node(bool value) : a1(value), ax(1) {}
Node(i64 a1, i64 ax) : a1(a1), ax(ax) {}
Node operator*(const Node &rhs) const {
return {(a1 * rhs.ax + ax * rhs.a1) % MOD, ax * rhs.ax * 2 % MOD};
}
};
struct SegmentTree {
std::vector<Node> values;
i64 offset;
SegmentTree() : values{}, offset{0} {}
explicit SegmentTree(size_t sz) : values(2 * sz), offset(sz) {}
void update(i64 idx, bool value) {
idx += offset;
values[idx] = Node(value);
while (idx /= 2) {
values[idx] = values[2 * idx] * values[2 * idx + 1];
}
}
const Node &root() const { return values[1]; }
};
int n, m;
std::vector<int> p, a;
SegmentTree st;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N;
m = M;
p = P;
a = A;
st = SegmentTree(N + 1);
for (i64 i = 0; i < M; i++) {
st.update(i, A[i]);
}
}
int count_ways(int l, int r) {
r += 1;
l -= n;
r -= n;
for (i64 i = l; i < r; i++) st.update(i, a[i] = !a[i]);
return st.root().a1;
}
Compilation message (stderr)
circuit.cpp: In function 'int count_ways(int, int)':
circuit.cpp:64:51: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
64 | for (i64 i = l; i < r; i++) st.update(i, a[i] = !a[i]);
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |