Submission #1100098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100098		vjudge1	XORanges (eJOI19_xoranges)	C++17	100 / 100	443 ms	25172 KiB

xoranges

#include <iostream>
#include <map>
#include <unordered_map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
#define ll long long
#define PLL pair<ll, ll>
#define PB push_back
#define F first
#define S second
#define MP make_pair
const ll INF = 999999999999999999;
const ll M = 1000000000+7;

ll binExp(ll a, ll b){
    if(a==1){
        return 1;
    }
    if(b==0){
        return 1;
    }
    ll ans = 1;
    if(b%2==1){
        ans = a;
    }
    return (binExp((a*a)%M,b/2)*ans)%M;
}

// t.F -> grab indexes 0,2,4,...
// t.S -> grab indexes 1,3,5,...
void build(ll v, ll l, ll r, vector<PLL> &t, vector<ll> &a){
    if(l==r){
        t[v].F = a[l];
        t[v].S = 0;
        return;
    }
    ll m = (l+r)/2;
    build(2*v,l,m,t,a);
    build(2*v+1,m+1,r,t,a);
    if(l%2!=m%2){
        t[v].F = t[2*v].F^t[2*v+1].F;
        t[v].S = t[2*v].S^t[2*v+1].S;
    }
    else{
        t[v].F = t[2*v].F^t[2*v+1].S;
        t[v].S = t[2*v].S^t[2*v+1].F;
    }
}

void update(ll v, ll l, ll r, ll lx, ll pr, ll x, vector<PLL> &t){
    if(l>lx or r<lx){
        return;
    }
    if(l%2==lx%2){
        t[v].F = t[v].F^pr^x;
    }
    else{
        t[v].S = t[v].S^pr^x;
    }
    if(l==r){
        return;
    }
    ll m = (l+r)/2;
    update(2*v,l,m,lx,pr,x,t);
    update(2*v+1,m+1,r,lx,pr,x,t);
}

ll XoR(ll v, ll l, ll r, ll lx, ll rx, vector<PLL> &t){
    //cout<<v<<" "<<l<<" "<<r<<endl;
    if(lx<=l and r<=rx){
        if((lx%2)==(l%2)){
            return t[v].F;
        }
        else{
            return t[v].S;
        }
    }
    if(l>rx or r<lx){
        return 0;
    }
    ll m = (l+r)/2;
    return (XoR(2*v,l,m,lx,rx,t)^XoR(2*v+1,m+1,r,lx,rx,t));
}


void solve(ll n, ll q, vector<ll> &a, vector<ll> &type, vector<PLL> &values){
    vector<PLL> t(4*n);
    build(1,0,n-1,t,a);

    for(ll i=0; i<q; i++){
        //cout<<i<<endl;
        if(type[i]==1){
            values[i].F--;
            update(1,0,n-1,values[i].F,a[values[i].F],values[i].S,t);
            a[values[i].F] = values[i].S;
        }
        else{
            values[i].F--;
            values[i].S--;
            if((values[i].S-values[i].F+1)%2==0){
                cout<<0<<endl;
            }
            else{
                cout<<XoR(1,0,n-1,values[i].F,values[i].S,t)<<endl;
            }
        }
    }
}

int main(){
    ll n,q;
    cin>>n>>q;
    vector<ll> a(n);
    for(ll i=0; i<n; i++){
        cin>>a[i];
    }
    vector<ll> type(q);
    vector<PLL> ranges(q);
    for(ll i=0; i<q; i++){
        cin>>type[i]>>ranges[i].F>>ranges[i].S;
    }
    solve(n,q,a,type,ranges);
}

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