Submission #759813

#	Time	Username	Problem	Language	Result	Execution time	Memory
759813		ivaziva	XORanges (eJOI19_xoranges)	C++14	100 / 100	471 ms	16836 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

#define MAXN 200010

long long n;
long long q;
long long niz[MAXN];
long long segment[4*MAXN];
queue<pair<long long,long long>> neparni;
queue<pair<long long,long long>> parni;
long long mesta[MAXN];

void build(long long node,long long l,long long r)
{
    if (l==r) segment[node]=niz[l];
    else
    {
        long long mid=(l+r)/2;
        build(2*node,l,mid);
        build(2*node+1,mid+1,r);
        segment[node]=segment[2*node]^segment[2*node+1];
    }
}

void update(long long node,long long l,long long r,long long pos,long long val)
{
    if (l==r) segment[node]=val;
    else
    {
        long long mid=(l+r)/2;
        if (pos<=mid) update(2*node,l,mid,pos,val);
        else update(2*node+1,mid+1,r,pos,val);
        segment[node]=segment[2*node]^segment[2*node+1];
    }
}

long long sol(long long node,long long l,long long r,long long a,long long b)
{
    if (a>b) return 0;
    if (l==a and r==b) return segment[node];
    long long mid=(l+r)/2;
    return sol(2*node,l,mid,a,min(mid,b))^sol(2*node+1,mid+1,r,max(mid+1,a),b);
}

int main()
{
    cin>>n>>q;
    for (long long i=1;i<=n;i++)
    {
        long long x;
        cin>>x;
        if (i%2==0) parni.push({x,i});
        else neparni.push({x,i});
    }
    long long pos=1;
    while (neparni.empty()==false)
    {
        niz[pos]=neparni.front().first;
        mesta[neparni.front().second]=pos;
        neparni.pop();
        pos++;
    }
    while (parni.empty()==false)
    {
        niz[pos]=parni.front().first;
        mesta[parni.front().second]=pos;
        parni.pop();
        pos++;
    }
    build(1,1,n);
    /*for (long long i=1;i<=n;i++) cout<<niz[i]<<" ";
    cout<<endl;
    for (long long i=1;i<=n;i++) cout<<mesta[i]<<" ";
    cout<<endl;*/
    for (long long i=1;i<=q;i++)
    {
        long long t;
        cin>>t;
        long long a;
        long long b;
        cin>>a>>b;
        if (t==1) update(1,1,n,mesta[a],b);
        else
        {
            //cout<<mesta[a]<<" "<<mesta[b]<<endl;
            if ((b-a+1)%2==1) cout<<sol(1,1,n,mesta[a],mesta[b])<<endl;
            else cout<<0<<endl;
        }
    }
}

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