oj.uz

Submission #797701

# Submission time Handle Problem Language Result Execution time Memory
797701 2023-07-29T19:15:36 Z jakobrs Digital Circuit (IOI22_circuit) C++17
16 / 100
 817 ms 5716 KB 
#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.0

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

Subtask #2
0 / 7.0

# 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 0 ms 208 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 208 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 -

Subtask #3
0 / 9.0

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

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 2888 KB Output is correct
2 Correct 626 ms 5708 KB Output is correct
3 Correct 754 ms 5688 KB Output is correct
4 Correct 664 ms 5680 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 2888 KB Output is correct
2 Correct 626 ms 5708 KB Output is correct
3 Correct 754 ms 5688 KB Output is correct
4 Correct 664 ms 5680 KB Output is correct
5 Correct 576 ms 3024 KB Output is correct
6 Correct 669 ms 5668 KB Output is correct
7 Correct 817 ms 5716 KB Output is correct
8 Correct 785 ms 5664 KB Output is correct
9 Correct 369 ms 336 KB Output is correct
10 Correct 589 ms 592 KB Output is correct
11 Correct 778 ms 548 KB Output is correct
12 Correct 693 ms 592 KB Output is correct

Subtask #6
0 / 27.0

# 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 0 ms 208 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 0 ms 208 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 -

Subtask #7
0 / 28.0

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

Subtask #8
0 / 11.0

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