Submission #797696

#TimeUsernameProblemLanguageResultExecution timeMemory
797696jakobrsDigital Circuit (IOI22_circuit)C++17
4 / 100
822 ms5712 KiB
#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] = true; toggled[2 * v + 1] = true; 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; 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; st.toggle_range(l, r); return st.root().a1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...