Submission #1043664

#	Time	Username	Problem	Language	Result	Execution time	Memory
1043664		biserailieva	XORanges (eJOI19_xoranges)	C++14	100 / 100	366 ms	13140 KiB

xoranges

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
int seg1[600009];
int seg2[600009];
int v[600009];
 
void build(int id, int l, int r)
{
    if(l==r)
    {
        if(l%2==1)
        {
            return;
        }
        seg1[id]=v[l];
        return;
    }
    int mid=(l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    seg1[id]=seg1[id*2]^seg1[id*2+1];
}
 
void update(int l, int r, int u, int v, int k)
{
    if(l==r && l==v)
    {
        seg1[u]=k;
        return;
    }
    if(v<l || v>r)
    {
        return;
    }
    int mid=(l+r)/2;
    update(l, mid, u*2, v, k);
    update(mid+1, r, u*2+1, v, k);
    seg1[u]=seg1[u*2]^seg1[u*2+1];
}
 
int query(int id, int l, int r, int a, int b, int res)
{
    if(a<=l && b>=r)
    {
        return seg1[id]^res;
    }
    if(l>b || r<a)
    {
        return res;
    }
    int mid=(l+r)/2;
    res=query(id*2, l, mid, a, b, res);
    res=query(id*2+1, mid+1, r, a, b, res);
    return res;
}
 
void build2(int id, int l, int r)
{
    if(l==r)
    {
        if(l%2==0)
        {
            return;
        }
        seg2[id]=v[l];
        return;
    }
    int mid=(l+r)/2;
    build2(id*2, l, mid);
    build2(id*2+1, mid+1, r);
    seg2[id]=seg2[id*2]^seg2[id*2+1];
}
 
void update2(int l, int r, int u, int v, int k)
{
    if(l==r && l==v)
    {
        seg2[u]=k;
        return;
    }
    if(v<l || v>r)
    {
        return;
    }
    ll mid=(l+r)/2;
    update2(l, mid, u*2, v, k);
    update2(mid+1, r, u*2+1, v, k);
    seg2[u]=seg2[u*2]^seg2[u*2+1];
}
 
int query2(int id, int l, int r, int a, int b, int res)
{
    if(a<=l && b>=r)
    {
        return seg2[id]^res;
    }
    if(l>b || r<a)
    {
        return res;
    }
    ll mid=(l+r)/2;
    res=query2(id*2, l, mid, a, b, res);
    res=query2(id*2+1, mid+1, r, a, b, res);
    return res;
}
 
int main()
{
    int n, q;
    cin>>n>>q;
    for(int i=0;i<n;i++)
    {
        cin>>v[i];
    }
    build(1, 0, n-1);
    build2(1, 0, n-1);
    while(q--)
    {
        int x, l, r;
        cin>>x>>l>>r;
        if(x==1)
        {
            l--;
            if(l%2==0)
            {
                update(0, n-1, 1, l, r);
            }
            else
            {
                update2(0, n-1, 1, l, r);
            }
        }
        else
        {
            l--;
            r--;
            if((r-l)%2==1)
            {
                cout<<0<<endl;
            }
            else
            {
                if(l%2==0)
                {
                    cout<<query(1, 0, n-1, l, r, 0)<<endl;
                }
                else
                {
                    cout<<query2(1, 0, n-1, l, r, 0)<<endl;
                }
            }
        }
    }
    return 0;
}

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