Submission #1221537

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221537		veham	XORanges (eJOI19_xoranges)	C++20	100 / 100	370 ms	5748 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
#define par(x) (bool(x&1) ? Ao : Ae)

int query(vi &A, int n2, int l, int u){
    l += n2 - 1;
    u += n2 - 1;
    int ans = 0;
    for(;u > l;(l = (l+1)>>1),(u = (u-1)>>1)){
        if(l % 2)    ans ^= A[l];
        if(!(u % 2)) ans ^= A[u];
    }
    if(u == l) ans ^= A[u];
    return ans;
}

int main(){
    int n,q;
    cin >> n >> q;
    int n2 = 1 << int(ceil(log2(n)));
    vi Ao(2*n2,0),Ae(2*n2,0);
    for(int i = 0;i < n;i++) cin >> par(i)[n2+i];
    for(int i = n2-1;i;i--) Ao[i] = (Ao[i<<1] ^ Ao[(i<<1) + 1]),Ae[i] = (Ae[i<<1] ^ Ae[(i<<1) + 1]);
    int t,i,j,u,l,m;
    while(q--){
        cin >> t;
        if(t == 1){
            cin >> i >> j;
            i += n2 - 1;
            j ^= par(i)[i];
            for(int i2 = i;i2;i2>>=1) par(i)[i2] ^= j;
        }
        else{
            cin >> l >> u;
            if((u - l) % 2){
                cout << 0 << '\n';
            }
            else{
                cout << query(par(l+1),n2,l,u) << '\n';
            }
        }
    }
    return 0;
}

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