Submission #925437

#	Time	Username	Problem	Language	Result	Execution time	Memory
925437		Karoot	XORanges (eJOI19_xoranges)	C++17	100 / 100	277 ms	12040 KiB

xoranges

#include <iostream>
#include <cmath>
#include <unordered_map>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <string>
#include <iomanip>
#include <algorithm>

#define all(x)  (x).begin(), (x).end()
#define rall(x)  (x).rbegin(), (x).rend()

using namespace std;

typedef long long ll;

ll linf = 1e15+1;

inline void scoobydoobydoo(){
    ios::sync_with_stdio(false);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
}

const int MAXN = 2e5+3;
ll vals[MAXN];

ll oddBIT[MAXN], evenBIT[MAXN];

void update(int node, ll val, bool isOdd){
    val ^= vals[node];
    while (node < MAXN){
        if (isOdd)oddBIT[node] ^= val;
        else evenBIT[node] ^= val;
        node += node&(~node+1);
    }
}

ll query(int l, int r, bool isOdd){
    ll over = 0;
    while (r){
        if (isOdd)over ^= oddBIT[r];
        else over ^= evenBIT[r];
        r -= r&(~r+1);
    }

    //cout << "over: " << over << endl;

    ll under = 0;
    l--;
    while (l){
        if (isOdd)under ^= oddBIT[l];
        else under ^= evenBIT[l];
        l -= l&(~l+1);
    }
    return over^under;
}



int main(){
    scoobydoobydoo();
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++){
        cin >> vals[i];
        update(i, 0, i%2);
    }

    /*for (int i = 1; i <= 2*n; i++){
        cout << i << ": " << oddBIT[i] << " " << evenBIT[i] << endl;
    }*/

    vector<int> ans;

    while (q--){
        int t; cin >> t;
        if (t == 1){
            int i, v; cin >> i >> v;
            update(i, v, i%2);
            vals[i] = v;
        } else {
            int l, r; cin >> l >> r;
            if ((r-l+1)%2 == 0)ans.push_back(0);
            else if (l == r)ans.push_back(vals[l]);
            else ans.push_back(query(l, r, r%2));
            //cout << query(l, r, l%2) << endl;
        }
    }

    for (ll x : ans)cout << x << endl;




    return 0;
}

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