Submission #345946

#	Time	Username	Problem	Language	Result	Execution time	Memory
345946		iliccmarko	XORanges (eJOI19_xoranges)	C++14	100 / 100	179 ms	11372 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
#define INF 1000000000
#define LINF 1000000000000000LL
#define pb push_back
#define all(x) x.begin(), x.end()
#define len(s) (int)s.size()
#define test_case { int t; cin>>t; while(t--)solve(); }
#define single_case solve();
#define line cerr<<"----------"<<endl;
#define ios { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cerr.tie(NULL); }
#define mod 1000000007LL
const int N = 2e5 + 5;
int segp[4*N], segn[4*N];
int n;
int a[N];

int buildp(int node, int l, int r)
{
    if(l==r)
    {
        if(l%2==1) return 0;
        return segp[node] = a[l];
    }
    int mid = (l+r)/2;
    return segp[node] = buildp(node*2+1, l, mid)^buildp(node*2+2, mid+1, r);
}

int buildn(int node, int l, int r)
{
    if(l==r)
    {
        if(l%2==0) return 0;
        return segn[node] = a[l];
    }
    int mid = (l+r)/2;
    return segn[node] = buildn(node*2+1, l, mid)^buildn(node*2+2, mid+1, r);
}

void updatep(int node, int l, int r, int pos, int x)
{
    if(l==r)
    {
        segp[node] = x;
        return;
    }
    int mid = (l+r)/2;
    if(pos>mid) updatep(node*2+2, mid+1, r, pos, x);
    else updatep(node*2+1, l, mid, pos, x);
    segp[node] = segp[node*2+1]^segp[node*2+2];
}

void updaten(int node, int l, int r, int pos, int x)
{
    if(l==r)
    {
        //cout<<"posatavio "<<pos<<" na"<<x<<endl;
        segn[node] = x;
        return;
    }
    int mid = (l+r)/2;
    if(pos>mid) updaten(node*2+2, mid+1, r, pos, x);
    else updaten(node*2+1, l, mid, pos, x);
    segn[node] = segn[node*2+1]^segn[node*2+2];
    //cerr<<l<<"      "<<r<<"          "<<segn[node]<<endl;
}

int get_xor(int node, int l, int r, int i, int j, int tip)
{
    if(i>r||j<l) return 0;
    if(i>=l&&j<=r)
    {
        if(tip==1) return segp[node];
        else {
            return segn[node];
        }
    }
    int mid = (i+j)/2;
    return get_xor(node*2+1, l, r, i, mid, tip)^get_xor(node*2+2, l, r, mid+1, j, tip);
}

int main()
{
    ios
    int q;
    cin>>n>>q;
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];
    }
    buildn(0, 1, n);
    buildp(0, 1, n);


    while(q--)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            int ind, val;
            cin>>ind>>val;
            if(ind%2==1) updaten(0, 1, n, ind, val); //cerr<<ind<<" "<<val<<endl;
            else updatep(0, 1, n, ind, val);
        }
        else
        {
            int l, r;
            cin>>l>>r;
            if((r-l+1)%2==0)
            {
                cout<<0<<endl;
            }
            else
            {
                if(l%2==1)
                {
                    //cout<<get_xor(0, 3, 3, 1, n, 2)<<" usao"<<endl;
                    cout<<get_xor(0, l, r, 1, n, 2)<<endl;
                }
                else
                {
                    cout<<get_xor(0, l, r, 1, n, 1)<<endl;
                }
            }
        }
    }




    return 0;
}

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