Submission #430837

#	Time	Username	Problem	Language	Result	Execution time	Memory
430837		NintsiChkhaidze	XORanges (eJOI19_xoranges)	C++14	100 / 100	207 ms	15880 KiB

xoranges

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define left (node<<1),l,((l+r)>>1)
#define right ((node<<1)|1),((l+r)>>1) + 1,r
using namespace std;
const int N = 200005;
ll odd[4*N],even[4*N],a[N];
bool D = 1;
void build(int node,int l,int r){
    if (l == r){
        if (l%2) odd[node] = a[l];
        else even[node] = a[l];
        return;
    }
    build(left),build(right);
    
    odd[node] = odd[(node<<1)]^odd[((node<<1)|1)];
    even[node] = even[(node<<1)]^even[((node<<1)|1)];
}
void upd(int node,int l,int r,int idx,ll val){
    if (l == r){
        if (l%2) odd[node] = val,even[node] = 0;
        else even[node] = val,odd[node] = 0;
        return;
    }
    if (idx > (l+r)>>1) upd(right,idx,val);
    else upd(left,idx,val);
    
    odd[node] = odd[(node<<1)]^odd[((node<<1)|1)];
    even[node] = even[(node<<1)]^even[((node<<1)|1)];
}
ll get(int node,int l,int r,int L,int R){
    if (r < L || R < l) return 0;
    if (L <= l && r <= R) {
        if (D) return odd[node];
        return even[node];
    }
    ll x = get(left,L,R),y = get(right,L,R);
    return x^y;
}
int main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
    int n,q;
    cin>>n>>q;
    
    for (int i=1;i<=n;i++)
        cin>>a[i];
        
    build(1,1,n);
    
    while(q--){
        int tp,x,y;
        cin>>tp>>x>>y;
        if (tp == 1) upd(1,1,n,x,y);
        else {
            D = 1;
            if (!(x%2)) D = 0;
            if ((y-x+1)%2) cout<<get(1,1,n,x,y)<<"\n";
            else cout<<0<<"\n";
        }
    }
}

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