oj.uz

Submission #742003

# Submission time Handle Problem Language Result Execution time Memory
742003 2023-05-15T10:49:25 Z bogdanvladmihai XORanges (eJOI19_xoranges) C++14
0 / 100
 145 ms 10292 KB 
#include <iostream>
#include <vector>

std::vector<int> tree[2];

void build(int p, int u, std::vector<int> &V, int l, int r) {
    if (l == r) {
        tree[p][u] = V[l];
        return;
    }
    int m = (l + r) / 2;
    build(p, 2 * u, V, l, m);
    build(p, 2 * u + 1, V, m + 1, r);
    tree[p][u] = tree[p][2 * u] ^ tree[p][2 * u + 1];
}

void update(int p, int u, int l, int r, int pos, int val) {
    if (l == r) {
        tree[p][u] = val;
        return;
    }
    int m = (l + r) / 2;
    if (pos <= m) {
        update(p, 2 * u, l, m, pos, val);
    } else {
        update(p, 2 * u + 1, m + 1, r, pos, val);
    }
    tree[p][u] = tree[p][2 * u] ^ tree[p][2 * u + 1];
}

int query(int p, int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return tree[p][u];
    }
    int m = (l + r) / 2;
    int lSide = 0, rSide = 0;
    if (ql <= m) {
        lSide = query(p, 2 * u, l, m, ql, qr);
    }
    if (qr > m) {
        rSide = query(p, 2 * u + 1, m + 1, r, ql, qr);
    }
    return lSide ^ rSide;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int N, Q;
    std::cin >> N >> Q;
    std::vector<int> V(N);
    for (int &x : V) {
        std::cin >> x;
    }

    std::vector<int> A, B;
    for (int i = 0; i < N; i++) {
        (i % 2 == 0 ? A : B).push_back(V[i]);
    }
    tree[0].resize(4 * N);
    tree[1].resize(4 * N);
    build(0, 1, A, 0, (int)A.size() - 1);
    build(1, 1, B, 0, (int)B.size() - 1);

    for (int q = 0; q < Q; q++) {
        int op, a, b;
        std::cin >> op >> a >> b;
        a--;
        b--;
        int posA = a / 2;
        int posB = b / 2;
        int size = (a % 2 == 0 ? A.size() : B.size()) - 1;
        if (op == 1) {
            update(a % 2, 1, 0, size, posA, b + 1);
        } else {
            std::cout << (b - a % 2 == 1 ? 0 :
                          query(a % 2, 1, 0, size, posA, posB)) << "\n";
        }
    }

    return 0;
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 145 ms 10292 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -