Submission #797701

#	Time	Username	Problem	Language	Result	Execution time	Memory
797701		jakobrs	Digital Circuit (IOI22_circuit)	C++17	16 / 100	817 ms	5716 KiB

circuit

#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;

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;
}

• Subtask 1: 0 / 2
• Subtask 2: 0 / 7
• Subtask 3: 0 / 9
• Subtask 4: 4 / 4
• Subtask 5: 12 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11