Submission #978054

#	Time	Username	Problem	Language	Result	Execution time	Memory
978054		SeenSiravit	XORanges (eJOI19_xoranges)	C++14	100 / 100	146 ms	12372 KiB

xoranges

#include<bits/stdc++.h>
#define ll long long

using namespace std;

const int mxN = 2e5 + 5;

void update(int l,int r, int idx , int val , int node , vector<int>& seg){
    if(l>idx || r<idx) return ;

    if(l == r){
        seg[node] = val;
        return ;
    }

    int mid = (l + r) / 2;

    update(l,mid , idx,val , node*2 ,seg);
    update(mid+1,r, idx,val , node*2 + 1,seg);

    seg[node] = seg[node*2] ^ seg[node*2 + 1];
}

int query(int l,int r, int curr_l , int curr_r , int node ,vector<int>& seg){
    if(curr_l>r || curr_r<l) return 0;
    if(l<=curr_l && curr_r<=r) return seg[node];

    int mid = (curr_l + curr_r) / 2;

    return query(l,r,curr_l,mid , node*2 ,seg) ^ query(l,r,mid+1,curr_r,node*2 + 1  , seg);
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0);

    int n,q;
    
    cin>> n >> q;

    vector<int> segA(4*n , 0);
    vector<int> segB(4*n , 0);

    for(int i=1;i<=n;i++){
        int val;
        cin>> val;

        if(i%2 == 1) update(1,n,i,val,1,segA);
        else update(1,n,i,val,1,segB);
    }


    while(q--){
        int cmd;
        cin>> cmd;

        if(cmd == 1){
            int idx,val;
            cin>> idx >> val;

            if(idx%2 == 1) update(1,n,idx,val,1,segA);
            else update(1,n,idx,val,1,segB);

        }else{
            int l,r;
            cin>> l >> r;

            int len = r-l+1;

            if(len % 2 == 0) cout<< 0 << "\n";
            else{
                if(l%2 == 1) cout<< query(l,r,1,n,1,segA) << "\n";
                else cout<< query(l,r,1,n,1,segB) << "\n";
            }
        }
    }


    return 0;
}

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