Submission #978035

#	Time	Username	Problem	Language	Result	Execution time	Memory
978035		SeenSiravit	XORanges (eJOI19_xoranges)	C++14	75 / 100	129 ms	11348 KiB

xoranges

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

using namespace std;

const int mxN = 2e5 + 5;

int n;
ll a[mxN][2];

ll seg[mxN * 2][2];

void build(int l , int r , int node , int t){
    if(l==r){
        seg[node][t] = a[l][t];
        return ;
    }

    int mid = (l + r) / 2;

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

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

void update(int l , int r, int idx, int node , ll val , int t){
    if(l>idx || r<idx) return ;

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

    int mid = (l+r)/2;

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

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

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

    int mid = (curr_l + curr_r) / 2;
    
    return query(l,r,curr_l,mid,node*2,t) ^ query(l,r,mid+1,curr_r,node*2 + 1,t);
}

void display(){
    cout<< "\ndisplay\n";
    cout<< 1 << "\n";
    for(int i=1;i<=n;i++) cout<< a[i][1] << " ";
    cout<< "\n";
    for(int i=1;i<=2*n;i++) cout<< seg[i][1] << " ";

    cout<< "\n2\n";
    for(int i=1;i<=n;i++) cout<< a[i][0] << " ";
    cout<< "\n";
    for(int i=1;i<=2*n;i++) cout<< seg[i][0] << " ";
    cout<< "\n";
}

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

    int q;

    cin>> n >> q;

    for(int i=1;i<=n;i++) cin>> a[i][i&1];

    build(1 , n , 1 , 1);
    build(1 , n , 1 , 0);

    // cout<< "before \n";
    // display();

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

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

            update(1,n,idx,1,val,idx&1);

            // display();
        }else{
            int l,r;
            cin>> l >> r;

            int len = r-l+1;

            // cout<< "ans = ";

            if(len%2 == 0){
                cout<< 0 << '\n';
                continue;
            }

            if(len & 1) cout<< query(l,r,1,n,1,l&1) << "\n";
            else cout<< query(l,r,1,n,1,l&1) << "\n";
        }
    }


    return 0;
}

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