Submission #286512

#	Time	Username	Problem	Language	Result	Execution time	Memory
286512		MasterTaster	XORanges (eJOI19_xoranges)	C++14	100 / 100	942 ms	11128 KiB

xoranges

#include <bits/stdc++.h>
#define MAXN 200007

using namespace std;

long long n, q, arr[MAXN], bitEven[MAXN], bitOdd[MAXN];

void updEven(int x, int v)
{
    while (x<MAXN)
    {
        bitEven[x]^=v;
        x+=x&(-x);
    }
}
void updOdd(int x, int v)
{
    while (x<=MAXN)
    {
        bitOdd[x]^=v;
        x+=x&(-x);
    }
}

int xorEven(int x)
{
    long long ress=0;
    while (x)
    {
        ress^=bitEven[x];
        x-=x&(-x);
    }

    return ress;
}
int xorOdd(int x)
{
    long long ress=0;
    while (x)
    {
        ress^=bitOdd[x];
        x-=x&(-x);
    }

    return ress;
}

int main()
{
    cin>>n>>q;

    for (int i=1; i<=n; i++)
    {
        cin>>arr[i];
        if (i%2==0)
        {
            updEven(i, arr[i]);
            updOdd(i, 0);
        }
        if (i%2==1)
        {
            updOdd(i, arr[i]);
            updEven(i, 0);
        }
    }

    while (q--)
    {
        int t;
        cin>>t;
        if (t==1)
        {
            int x, y;
            cin>>x>>y;
            if (x%2==0) updEven(x, y^arr[x]);
            else updOdd(x, y^arr[x]);
            arr[x]=y;
        }
        else
        {
            int l, r;
            cin>>l>>r;
            if ((r-l+1)%2==0) cout<<0<<endl;
            else
            {
                if (l%2==0)
                {
                    if (l==2) cout<<xorEven(r)<<endl;
                    else cout<<(xorEven(r)^xorEven(l-2))<<endl;
                }
                else
                {
                    if (l==1) cout<<xorOdd(r)<<endl;
                    else cout<<(xorOdd(r)^xorOdd(l-2))<<endl;
                }
            }
        }
    }
}

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