Submission #1176727

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176727		AlgorithmWarrior	XORanges (eJOI19_xoranges)	C++20	100 / 100	306 ms	6484 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

/// lungime para => 0
/// lungime impara => 101010101...101010101

int const MAX=2e5+5;
int n,m;
int v[MAX];

struct AINT{
    int par[4*MAX],impar[4*MAX];
    void update(int nod,int st,int dr,int poz,int val){
        if(st==dr){
            if(poz%2==0)
                par[nod]=val;
            else
                impar[nod]=val;
        }
        else{
            int mij=(st+dr)/2;
            if(poz<=mij)
                update(2*nod,st,mij,poz,val);
            else
                update(2*nod+1,mij+1,dr,poz,val);
            par[nod]=(par[2*nod]^par[2*nod+1]);
            impar[nod]=(impar[2*nod]^impar[2*nod+1]);
        }
    }
    int query(int nod,int st,int dr,int a,int b,bool tip){
        if(a<=st && dr<=b)
            return tip?impar[nod]:par[nod];
        int xorr=0;
        int mij=(st+dr)/2;
        if(a<=mij)
            xorr^=query(2*nod,st,mij,a,b,tip);
        if(b>mij)
            xorr^=query(2*nod+1,mij+1,dr,a,b,tip);
        return xorr;
    }
}aint;

void read(){
    cin>>n>>m;
    int i;
    for(i=1;i<=n;++i){
        cin>>v[i];
        aint.update(1,1,n,i,v[i]);
    }
}

void process_queries(){
    int i;
    for(i=1;i<=m;++i){
        int type;
        cin>>type;
        if(type==1){
            int ind,val;
            cin>>ind>>val;
            aint.update(1,1,n,ind,val);
        }
        else{
            int l,r;
            cin>>l>>r;
            int len=r-l+1;
            if(len%2==0)
                cout<<0<<'\n';
            else
                cout<<aint.query(1,1,n,l,r,l%2)<<'\n';
        }
    }
}

int main()
{
    read();
    process_queries();
    return 0;
}

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