Submission #1219808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219808		Aisha	XORanges (eJOI19_xoranges)	C++20	55 / 100	26 ms	7492 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

#define int long long

int N = 100005;
vector <int> a(N);
vector <pair <int, int>> t(4 * N, {0, 0});

void build(int i, int l, int r) {
    if (l == r) {
        if (l % 2 == 1) t[i].first = a[l];
        else t[i].second = a[l];
        
        return;
    }

    int m = (l + r) / 2;
    build(i * 2, l, m);
    build(i * 2 + 1, m + 1, r);

    t[i].first = t[i * 2].first ^ t[i * 2 + 1].first;
    t[i].second = t[i * 2].second ^ t[i * 2 + 1].second;
}

void update(int i, int l, int r, int ind, int x) {
    if (l == r) {
        if (l % 2 == 1) t[i].first = x;
        else t[i].second = x;

        return;
    }
    int m = (l + r) / 2;

    if (ind <= m) update(i * 2, l, m, ind, x);
    else update(i * 2 + 1, m + 1, r, ind, x);

    t[i].first = t[i * 2].first ^ t[i * 2 + 1].first;
    t[i].second = t[i * 2].second ^ t[i * 2 + 1].second;
}

pair <int, int> get(int i, int tl, int tr, int ql, int qr) {
    pair <int, int> p = {0ll, 0ll};
    if (tr < ql || qr < tl) return p;
    if (tl == ql && tr == qr) return t[i];

    int m = (tl + tr) / 2;
    if (qr <= m) return get(i * 2, tl, m, ql, qr);
    if (ql > m) return get(i * 2 + 1, m + 1, tr, ql, qr);

    pair <int, int> p1 = get(i * 2, tl, m, ql, m);
    pair <int, int> p2 = get(i * 2 + 1, m + 1, tr, m + 1, qr);
    pair <int, int> p3 = {p1.first ^ p2.first, p1.second ^ p2.second};
    return p3;
}

signed main() {
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i ++) cin >> a[i];
    build(1, 1, n);

    while (q --) {
        int op; cin >> op;

        if (op == 1) {
            int i, x; cin >> i >> x;

            update(1, 1, n, i, x);
        } else {
            int l, r; cin >> l >> r;
            if (r % 2 != l % 2) {
                cout << 0 << endl;
                continue;
            }

            pair <int, int> ans = get(1, 1, n, l, r);
            if (l % 2) cout << ans.first << endl;
            else cout << ans.second << endl;
        }
    }

    return 0;
}

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