Submission #741998

#	Time	Username	Problem	Language	Result	Execution time	Memory
741998		bogdanvladmihai	XORanges (eJOI19_xoranges)	C++14	0 / 100	152 ms	10340 KiB

xoranges

#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;
        int posA = a / 2 - (1 - a % 2);
        int posB = b / 2 - (1 - b % 2);
        a--;
        b--;
        if (op == 1) {
            update(a % 2, 1, 0, (a % 2 == 0 ? A.size() : B.size()) - 1, posA, b + 1);
        } else {
            std::cout << (b - a % 2 == 1 ? 0 : query(a % 2, 1, 0, (a % 2 == 0 ? A.size() : B.size()) - 1, posA, posB)) << "\n";
        }
    }

    return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 18
• Subtask 3: 0 / 25
• Subtask 4: 0 / 20
• Subtask 5: 0 / 25