Submission #1219293

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219293		mariamtsagareli	XORanges (eJOI19_xoranges)	C++20	100 / 100	56 ms	4364 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
using ui = unsigned int;

struct f1{
    int n;
    vector<ui> f;
    f1(int _n): n(_n), f(n+1, 0) {}
    void upd(int i, ui v) {
        for (; i <= n; i += i & -i)
            f[i] ^= v;
    }
    ui qry(int i) {
        ui s = 0;
        for (; i > 0; i -= i & -i)
            s ^= f[i];
        return s;
    }
    ui range(int l, int r) {
        return qry(r) ^ qry(l - 1);
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    f1 odd(n), even(n);
    for(int i = 1; i <= n; i++){
        if(i & 1) odd.upd(i, a[i]);
        else      even.upd(i, a[i]);
    }

    while(q--){
        int t;
        cin >> t;
        if(t == 1){
            int i; ui x;
            cin >> i >> x;
            ui old = a[i];
            if(i & 1) odd.upd(i, old ^ x);
            else      even.upd(i, old ^ x);
            a[i] = x;
        } else {
            int l, r;
            cin >> l >> r;
            int len = r - l + 1;
            if((len & 1) == 0){
                cout << 0u << "\n";
            } else if(l & 1){
                cout << odd.range(l, r) << "\n";
            } else {
                cout << even.range(l, r) << "\n";
            }
        }
    }

    return 0;
}

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