Submission #810981

#	Time	Username	Problem	Language	Result	Execution time	Memory
810981		andrewp	XORanges (eJOI19_xoranges)	C++17	100 / 100	295 ms	11212 KiB

xoranges

//Dedicated to my love, ivaziva
#include <bits/stdc++.h>

using namespace std;
int n,q;
const int ivamanjeod3=200007;
int iva[ivamanjeod3],ivapavODD[ivamanjeod3*4],ivapavEVEN[ivamanjeod3*4];
void IVAIVA(int v,int tl,int tr,int i,int x)
{
    if(tl==tr)
    {
        if(tl%2==1)
        {
            ivapavODD[v]=x;
            ivapavEVEN[v]=0;
        }
        else
        {
            ivapavEVEN[v]=x;
            ivapavODD[v]=0;
        }
        return;
    }
    int mid=(tl+tr)/2;
    if(i<=mid) IVAIVA(2*v,tl,mid,i,x);
    else IVAIVA(2*v+1,mid+1,tr,i,x);
    ivapavODD[v]=(ivapavODD[2*v]^ivapavODD[2*v+1]);
    ivapavEVEN[v]=(ivapavEVEN[2*v]^ivapavEVEN[2*v+1]);
}
int IVAIVAIVA1(int v,int tl,int tr,int l,int r)
{
    if(l>r) return 0;
    if(tl==l&&tr==r) return ivapavODD[v];
    int mid=(tl+tr)/2;
    return (IVAIVAIVA1(2*v,tl,mid,l,min(mid,r))^IVAIVAIVA1(2*v+1,mid+1,tr,max(mid+1,l),r));
}
int IVAIVAIVA2(int v,int tl,int tr,int l,int r)
{
    if(l>r) return 0;
    if(tl==l&&tr==r) return ivapavEVEN[v];
    int mid=(tl+tr)/2;
    return (IVAIVAIVA2(2*v,tl,mid,l,min(mid,r))^IVAIVAIVA2(2*v+1,mid+1,tr,max(mid+1,l),r));
}
void IVA(int v,int tl,int tr)
{
    if(tl==tr){
        if(tl%2==1)
        {
            ivapavODD[v]=iva[tl];
            ivapavEVEN[v]=0;
        }
        else
        {
            ivapavODD[v]=0;
            ivapavEVEN[v]=iva[tl];
        }
        return;
    }
    int mid=(tl+tr)/2;
    IVA(2*v,tl,mid);
    IVA(2*v+1,mid+1,tr);
    ivapavODD[v]=ivapavODD[2*v]^ivapavODD[2*v+1];
    ivapavEVEN[v]=ivapavEVEN[2*v]^ivapavEVEN[2*v+1];
}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>iva[i];
    }
    IVA(1,1,n);
    while(q--)
    {
        int tp,l,r;
        cin>>tp>>l>>r;
        if(tp==1)
        {
            int i=l,x=r;
            IVAIVA(1,1,n,i,x);
        }
        else
        {
            int sz=r-l+1;
            if(sz%2==0)
            {
                cout<<0<<endl;
            }
            else
            {
                if(l%2==1)
                {
                    cout<<IVAIVAIVA1(1,1,n,l,r)<<endl;
                }
                else
                {
                    cout<<IVAIVAIVA2(1,1,n,l,r)<<endl;
                }
            }
        }
    }
    return 0;
}

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