Submission #623777

#	Time	Username	Problem	Language	Result	Execution time	Memory
623777		fabijan_cikac	XORanges (eJOI19_xoranges)	C++17	100 / 100	140 ms	9548 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

const int BIT = 18;
const int N = (1 << BIT);

int n, q;
int t[2][2 * N] = { 0 };

void update(int x, int pos, int val){
    t[x][pos] = val; pos /= 2;
    while (pos > 0){
        t[x][pos] = (t[x][2 * pos] ^ t[x][2 * pos + 1]); pos /= 2;
    }
}

int query(int x, int u, int l, int r, int ql, int qr){
    if (ql > r || qr < l)
        return 0;
    if (ql >= l && qr <= r)
        return t[u][x];
    int mid = (ql + qr) / 2;
    return (query(2 * x, u, l, r, ql, mid) ^ query(2 * x + 1, u, l, r, mid + 1, qr));
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> q;
    for (int i = 0; i < n; ++i){
        int x; cin >> x;
        update(i & 1, N + i, x);
    }
    for (int i = 0; i < q; ++i){
        int u; cin >> u;
        if (u == 1){
            int pos, x; cin >> pos >> x;
            --pos; update(pos & 1, N + pos, x);
        }
        else{
            int l, r; cin >> l >> r; --l; --r;
            if ((r - l) & 1)
                cout << 0;
            else cout << query(1, l & 1, l + 1, r + 1, 1, N);
            cout << '\n';
        }
    }

    return 0;
}

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