Submission #1245279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245279		kchu_z	XORanges (eJOI19_xoranges)	C++20	100 / 100	104 ms	4440 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;

int a[100001][2], segment[400001][2];

int build(int idx, int l, int r, int s) {
    if (l == r) return segment[idx][s] = a[l][s];

    int m = (l + r) / 2;
    return segment[idx][s] = build(2 * idx, l, m, s) ^ build(2 * idx + 1, m + 1, r, s);
}

int query(int idx, int l, int r, int ql, int qr, int s) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return segment[idx][s];

    int m = (l + r) / 2;
    return query(2 * idx, l, m, ql, qr, s) ^ query(2 * idx + 1, m + 1, r, ql, qr, s);
}

int update(int idx, int l, int r, int pos, int val, int s) {
    if (pos < l || r < pos) return segment[idx][s];
    if (l == r) return segment[idx][s] = val;

    int m = (l + r) / 2;
    return segment[idx][s] = update(2 * idx, l, m, pos, val, s) ^ update(2 * idx + 1, m + 1, r, pos, val, s);
}

int main() {

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        cin >> a[(i + 1) / 2][i % 2];
    }

    build(1, 1, n / 2, 0);
    build(1, 1, n / 2 + n % 2, 1);

    while (q--) {
        int t, l, r;
        cin >> t >> l >> r;

        if (t == 1) {
            update(1, 1, n / 2 + (n % 2) * (l % 2), (l + 1) / 2, r, l % 2);
        } else {
            if ((r - l + 1) % 2 == 0) cout << 0 << '\n';
            else cout << query(1, 1, n / 2 + (n % 2) * (l % 2), (l + 1) / 2, (r + 1) / 2, l % 2) << '\n';
        }
    }

    return 0;

}

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