Submission #753090

#	Time	Username	Problem	Language	Result	Execution time	Memory
753090		MateiKing80	XORanges (eJOI19_xoranges)	C++14	100 / 100	532 ms	4400 KiB

xoranges

#include <iostream>

using namespace std;

int v[200005];
int aint1[1<<19];
int aint2[1<<19];


void build1(int poz, int st, int dr)
{
    if(st==dr)
    {
        aint1[poz]=v[2*st-1];
        return;
    }
    int mid=(st+dr)/2;
    build1(2*poz,st,mid);
    build1(2*poz+1,mid+1,dr);
    aint1[poz]=(aint1[2*poz]^aint1[2*poz+1]);
}

void build2(int poz, int st, int dr)
{
    if(st==dr)
    {
        aint2[poz]=v[2*st];
        return;
    }
    int mid=(st+dr)/2;
    build2(2*poz,st,mid);
    build2(2*poz+1,mid+1,dr);
    aint2[poz]=(aint2[2*poz]^aint2[2*poz+1]);
}


void update1(int poz, int st, int dr, int a, int b)
{
    if(st==dr)
    {
        aint1[poz]=b;
        return;
    }
    int mid=(st+dr)/2;
    if(a<=mid)
        update1(2*poz,st,mid,a,b);
    else
        update1(2*poz+1,mid+1,dr,a,b);
    aint1[poz]=(aint1[2*poz]^aint1[2*poz+1]);
}

void update2(int poz, int st, int dr, int a, int b)
{
    if(st==dr)
    {
        aint2[poz]=b;
        return;
    }
    int mid=(st+dr)/2;
    if(a<=mid)
        update2(2*poz,st,mid,a,b);
    else
        update2(2*poz+1,mid+1,dr,a,b);
    aint2[poz]=(aint2[2*poz]^aint2[2*poz+1]);
}


int query1(int poz, int st, int dr, int a, int b)
{
    if(a<=st && dr<=b)
        return aint1[poz];
    int mid=(st+dr)/2;
    if(b<=mid)
        return query1(2*poz,st,mid,a,b);
    if(mid<a)
        return query1(2*poz+1,mid+1,dr,a,b);
    return (query1(2*poz,st,mid,a,b)^query1(2*poz+1,mid+1,dr,a,b));
}

int query2(int poz, int st, int dr, int a, int b)
{
    if(a<=st && dr<=b)
        return aint2[poz];
    int mid=(st+dr)/2;
    if(b<=mid)
        return query2(2*poz,st,mid,a,b);
    if(mid<a)
        return query2(2*poz+1,mid+1,dr,a,b);
    return (query2(2*poz,st,mid,a,b)^query2(2*poz+1,mid+1,dr,a,b));
}




int main()
{
    int n,q;
    cin>>n>>q;
    for(int i=1;i<=n;i++)
        cin>>v[i];
    build1(1,1,(n+1)/2);
    build2(1,1,n/2);
    for(int i=0;i<q;i++)
    {
        int cer,a,b;
        cin>>cer>>a>>b;
        if(cer==1)
        {
            if( (a%2) == 1)
                update1(1,1,(n+1)/2,a/2+1,b);
            else
                update2(1,1,n/2,a/2,b);
        }
        else
        {
            if((b-a)%2==1)
                cout<<0<<'\n';
            else if((a%2)==1)
                cout<<query1(1,1,(n+1)/2,a/2+1,b/2+1)<<'\n';
            else
                cout<<query2(1,1,n/2,a/2,b/2)<<'\n';
        }
    }
}

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