Submission #579244

#	Time	Username	Problem	Language	Result	Execution time	Memory
579244		Kipras	XORanges (eJOI19_xoranges)	C++17	100 / 100	211 ms	12572 KiB

xoranges

#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const ll maxN = 2e5+10;

int l[maxN*2], r[maxN*2], val1[maxN*2], val0[maxN*2];

int ind = 1;
ll n, m;

void build(int v){
    if(v >= n){
        l[v] = ind;
        r[v] = ind;
        ind++;
        val0[v]=0;
        val1[v]=0;
    }else{
        build(v*2);
        build(v*2+1);
        l[v] = l[v*2];
        r[v] = r[v*2+1];
        //cout<<v<<" "<<l[v]<<" "<<r[v]<<endl;
    }
}

int query(int v, int L, int R){
    ll ret=0;
    if(L <= l[v] && r[v] <= R){
        if(L%2==0)ret = val0[v];
        else ret = val1[v];
        //cout<<"b";
    }else if(r[v] < L || R < l[v]){
        //cout<<"c";
        ret = 0;
    }else{
        //cout<<"d";
        ret = query(v*2, L, R)^query(v*2+1, L, R);
    }
    //cout<<ret<<" "<<v<<" "<<L<<" "<<R<<" "<<l[v]<<" "<<r[v]<<" "<<endl;
    return ret;
}

void change(int v, int L, int R, int x){

    if(L <= l[v] && r[v] <= R){
        val0[v]=0;
        val1[v]=0;
        if(l[v]%2==0)val0[v]=x;
        else val1[v]=x;
    }else if(r[v] < L || R < l[v]){

    }else{
        change(v*2, L, R, x);
        change(v*2+1, L, R, x);
        val0[v] = val0[v*2]^val0[v*2+1];
        val1[v] = val1[v*2]^val1[v*2+1];
    }
}



int main()
{

    ios_base::sync_with_stdio(0);cin.tie(nullptr);

    cin>>n>>m;

    build(1);

    for(int i = 1; i <= n; i++){
        ll aa;
        cin>>aa;
        change(1, i, i, aa);
    }

    for(int i = 1; i <= m; i++){
        ll op;
        cin>>op;
        if(op==2){
            ll aa, bb;
            cin>>aa>>bb;
            if(abs(aa-bb)%2==1){
                cout<<"0\n";
            }else{
                cout<<query(1, aa, bb)<<"\n";
            }
        }else{
            ll aa, bb;
            cin>>aa>>bb;
            change(1, aa, aa, bb);
        }
    }

    return 0;
}

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