Submission #577157

#	Time	Username	Problem	Language	Result	Execution time	Memory
577157		berr	XORanges (eJOI19_xoranges)	C++17	0 / 100	151 ms	6028 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
int st1[400005], st2[400005], t1[200005], t2[200005];

void build1(int l, int r, int v)
{
    if(l>r) return;
    else if(l==r) st1[v]=t1[l];
    else
    {
        int mid=(l+r)/2;
        build1(l, mid, v*2);
        build1(mid+1, r, v*2+1);
        st1[v]=(st1[v*2] xor st1[v*2+1]);
    }
}

void build2(int l, int r, int v)
{
    if(l>r) return;
    else if(l==r) st2[v]=t2[l];
    else
    {
        int mid=(l+r)/2;
        build2(l, mid, v*2);
        build2(mid+1, r, v*2+1);
        st2[v]=(st2[v*2] xor st2[v*2+1]);
    }
}



void update1(int l, int r, int v, int pos, int val)
{
    if(l>r)  return;
    else if(l==r)  t1[l]=st1[v]=val;
    else
    {
        if((l+r)/2>=pos) update1(l, (l+r)/2, v*2, pos, val);
        else update1((l+r)/2+1, r, v*2+1, pos, val);

        st1[v]=(st1[v*2] xor st1[v*2+1]);
    }

}

void update2(int l, int r, int v, int pos, int val)
{
    if(l>r)  return;
    else if(l==r)  t2[l]=st2[v]=val;
    else
    {
        if((l+r)/2>=pos) update2(l, (l+r)/2, v*2, pos, val);
        else update2((l+r)/2+1, r, v*2+1, pos, val);

        st2[v]=st2[v*2] xor st2[v*2+1];
    }

}

int get1(int l, int r, int tl, int tr, int v) 
{   

    if(l>tr||r<tl){ return 0;}
    if(tl<=l&&tr>=r){return st1[v];}
    return (get1(l, (l+r)/2, tl, tr, v*2) xor (get1((l+r)/2+1, r, tl, tr, v*2+1)));

}

int get2(int l, int r, int tl, int tr, int v) 
{
    if(l>tr||r<tl) return 0;
    if(tl<=l&&r<=tr) return st2[v];
    return (get2(l, (l+r)/2, tl, tr, v*2) xor (get2((l+r)/2+1, r, tl, tr, v*2+1)));

}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n, q; cin>>n>>q;

    int l=0, r=0;
    vector<int> a(n);

    for(int i=0; i<n; i++)
    {
        if(i%2==0) cin>>t1[l], l++, a[i]=t1[l-1];
        else cin>>t2[r], r++, a[i]=t2[r-1];
    }

    build1(0, l-1, 1);
    build2(0, r-1, 1);

    while(q--)
    {

        int x, y, z; cin>>x>>y>>z;
        y--;
        if(x==1)
        {
            a[y]=z;
            if(y%2==0) update1(0, l-1, 1, y/2, z);
            else{update2(0, r-1, 1, y/2, z);}


        }
        else
        {
            z--;
            if(z-y==1) cout<<0;
            else if((z-y+1)%2==1)
            {

                if(y%2==0)
                {

                    cout<<get1(0, l-1, y/2, z/2, 1);
                }
                else
                {
                    cout<<get2(0, r-1, y/2, z/2, 1);
                }
            }
            else
            {
                if((y+1)%2==1)
                {
                    cout<<get1(0, l-1, (y)/2, (z/2), 1);
                }
                else
                {
                    cout<<get2(0, l-1, (y)/2, (z/2), 1);

                }

            }
            cout<<"\n";
       /*     cout<<" ";
            int h=0;
            for(int l=1; l<=(z-y)+1; l++){
            for(int j=y; j+l-1<=z; j++){
            for(int i=j; i<=j+l-1; i++){ h=(h xor a[i]);}
            }}

                cout<<h<<"\n";
-*/
        }

    }

}

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