Submission #978050

#	Time	Username	Problem	Language	Result	Execution time	Memory
978050		SeenSiravit	XORanges (eJOI19_xoranges)	C++14	0 / 100	100 ms	6172 KiB

xoranges

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

using namespace std;

const int mxN = 2e5 + 5;

void build(int l,int r,int node,vector<int>& arr , vector<int>& seg){
    if(l == r){
        seg[node] = arr[l];
        return ;
    }

    int mid = (l + r) / 2;

    build(l,mid, node*2 , arr , seg);
    build(mid+1,r , node*2 + 1 , arr , seg);

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

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

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

    int mid = (l + r) / 2;

    update(l,mid , idx,val , node*2 , arr , seg);
    update(mid+1,r, idx,val , node*2 + 1 , arr , 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> a(n+1 , 0) , b(n+1 , 0);
    for(int i=1;i<=n;i++){
        if(i%2 == 1) cin>> a[i];
        else cin>> b[i];
    }

    vector<int> segA(n*2 + 1 + 5 , 0) , segB(n*2 + 1 + 5 , 0);
    build(1,n,1,a,segA);
    build(1,n,1,b,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,a,segA);
            else update(1,n,idx,val,1,b,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: 0 / 12
• Subtask 2: 0 / 18
• Subtask 3: 0 / 25
• Subtask 4: 0 / 20
• Subtask 5: 0 / 25