Submission #1147907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147907		mariza	XORanges (eJOI19_xoranges)	C++20	100 / 100	232 ms	15600 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define MID ((l+r)/2)
#define RANGE (r-l+1)

#define N 200001
#define INF 1000000000

ll arr[N], n, q;

struct node{
    ll val;
    node *L, *R;

    void build(bool odd, ll l, ll r){
        if(l==r){
            val=arr[2*l+odd];
        }
        else{
            L=new node;
            R=new node;
            L->build(odd,l,MID);
            R->build(odd,MID+1,r);
            val=L->val ^ R->val;
        }
    }

    ll query(ll tl, ll tr, ll l=0, ll r=n-1){
        if(tl<=l && r<=tr){
            return val;
        }
        else if(r<tl || tr<l){
            return 0;
        }
        else{
            return L->query(tl,tr,l,MID) ^ R->query(tl,tr,MID+1,r);
        }
    }

    void rescan(ll pos, ll nVal, ll l=0, ll r=n-1){
        if(l==pos && r==pos){
            val=nVal;
        }
        else if(l<=pos && pos<=r){
            L->rescan(pos, nVal, l, MID);
            R->rescan(pos, nVal, MID+1, r);
            val=L->val ^ R->val;
        }
    }
};

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

    cin>>n>>q;
    for(ll i=0; i<n; i++){
        cin>>arr[i];
    }

    node even, odd;
    even.build(false, 0, n/2+n%2-1);
    odd.build(true, 0, n/2-1);

    while(q--){
//        cout<<"Even:";
//        even.traverse();
//        cout<<"Odd:";
//        odd.traverse();
        ll k; cin>>k;
        if(k==1){
            ll i, j;
            cin>>i>>j; i--;
            if(i%2==0) even.rescan(i/2,j, 0, n/2+n%2-1);
            else odd.rescan(i/2,j,0,n/2-1);
        }
        else{
            ll l, r;
            cin>>l>>r; l--; r--;
            if(RANGE%2==0){
                cout<<0<<endl;
            }
            else{
                cout<<((l%2==0) ?even.query(l/2,r/2,0,n/2+n%2-1) :odd.query(l/2,r/2,0,n/2-1))<<endl;
            }
        }
    }

    return 0;
}

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