Submission #839311

#	Time	Username	Problem	Language	Result	Execution time	Memory
839311		raul2008487	XORanges (eJOI19_xoranges)	C++17	55 / 100	400 ms	7520 KiB

xoranges

#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define in insert
#define ld long double
#define ll long long
#define pii pair<ll,ll>
#define vl vector<ll>
#define mpr make_pair
#define fi first
#define se second
#define lg(a) __lg(a)
#define all(v) v.begin(),v.end()
//#define endl "\n"
using namespace std;
const int sz = 2e5+5;
const ll inf = 100000000000000005;
ll id[sz], a[sz], tree[sz];
void build(ll v, ll l, ll r){
    if(l==r){
        tree[v] = a[l];
        return ;
    }
    ll m = (l+r)>>1;
    build(v*2,l,m);
    build(v*2+1,m+1,r);
    tree[v] = (tree[v*2] ^ tree[v*2+1]);
}
void update(ll v, ll tl, ll tr, ll pos, ll val){
    if(tl > tr){return ;}
    if(tl == tr && tr == pos){
        tree[v] = val;
        a[tl] = val;
        return ;
    }
    ll tm = (tl+tr)>>1;
    if(pos <= tm){
        update(v*2,tl,tm,pos,val);
    }
    else{
        update(v*2+1,tm+1,tr,pos,val);
    }
    tree[v] = (tree[v*2] ^ tree[v*2+1]);
}
ll get(ll v, ll tl, ll tr, ll l, ll r){
    if(tl > r || tr < l){
        return 0;
    }
    if(tl >= l && tr <= r){
        return tree[v];
    }
    ll tm = (tl+tr)>>1;
    ll s1 = get(v*2,tl,tm,l,r);
    ll s2 = get(v*2+1,tm+1,tr,l,r);
    return (s1^s2);
}
void solve(){
    ll n,q,i,j,cur=0,l,r,qt;
    cin>>n>>q;
    vl v(n+1);
    for(i=1;i<=n;i++){
        cin>>v[i];
    }
    for(i=1;i<=n;i+=2){
        id[i] = ++cur;
        a[cur] = v[i];
    }
    for(i=2;i<=n;i+=2){
        id[i] = ++cur;
        a[cur] = v[i];
    }
    build(1,1,n);
    while(q--){
        cin>>qt;
        if(qt == 1){
            cin>>l>>r;
            update(1,1,n,id[l],r);
        }
        else{
            cin>>l>>r;
            if((r-l+1) % 2 == 0){cout << 0 << endl;continue;}
            cout << get(1,1,n,id[l],id[r]) << endl;
        }
    }
}
int main(){
    ll t=1;
    //cin>>t;
    while(t--){
        solve();
    }
}
/*
5 6
1 2 3 4 5
2 1 3
1 1 3
2 1 5
2 4 4
1 1 1
2 4 4

*/

Compilation message (stderr)

xoranges.cpp: In function 'void solve()':
xoranges.cpp:58:14: warning: unused variable 'j' [-Wunused-variable]
   58 |     ll n,q,i,j,cur=0,l,r,qt;
      |              ^

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