Submission #432100

#	Time	Username	Problem	Language	Result	Execution time	Memory
432100		Dakto	XORanges (eJOI19_xoranges)	C++17	100 / 100	774 ms	18704 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

struct segtree{
    int n;
    vector<int> v,l,r;
    
    segtree(int na){
        n=1<<int(ceil(log2(na)));
        v.resize(2*n);
        l.resize(2*n);
        r.resize(2*n);
        for(int i=0; i<n; i++) l[i+n]=r[i+n]=i;
        for(int i=n-1; i>0; i--){
            l[i]=l[2*i];
            r[i]=r[2*i+1];
        }
    }

    void set(int i, int val){
        i+=n;
        v[i]=val;
        i/=2;
        while(i){
            v[i]=v[2*i]^v[2*i+1];
            i/=2;
        }
    }

    int query(int left, int right, int u=1){
        if(left>r[u] || right < l[u]) return 0;
        if(left<=l[u] && right >=r[u]) return v[u];
        return query(left,right,2*u)^query(left,right,2*u+1);
    }
};

int main(){
    int n,q;
    cin>>n>>q;
    segtree even(n), odd(n);

    for(int i=0; i<n; i++){
        int t;
        cin>>t;
        if(i%2==0) even.set(i,t);
        else odd.set(i,t);
    }

    for(int i=0; i<q; i++){
        int t;
        cin>>t;
        if(t==1){
            int x,y;
            cin>>x>>y;
            x--;
            if(x%2==0) even.set(x,y);
            else odd.set(x,y);

        }
        else{
            int l,u;
            cin>>l>>u;
            l--;u--;
            if((u-l+1)%2==0){
                cout<<0<<endl;
                continue;
            }
            if(l%2==0) cout<<even.query(l,u)<<endl;
            else cout<<odd.query(l,u)<<endl;
        }
    }
}

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