Submission #798035

#	Time	Username	Problem	Language	Result	Execution time	Memory
798035		jakobrs	Digital Circuit (IOI22_circuit)	C++17	34 / 100	3078 ms	9308 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;

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 = 1; i < N + M; i++) {
            if (P[i] != (i - 1) / 2) {
                is_45 = false;
                break;
            }
        }
    } else {
        is_45 = false;
    }

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

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