Submission #637319

#	Time	Username	Problem	Language	Result	Execution time	Memory
637319		ksu2009en	XORanges (eJOI19_xoranges)	C++17	55 / 100	91 ms	5808 KiB

xoranges

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>

using namespace std;
typedef long long ll;

ll const dim = (ll)(2 * 1e5);

ll todd[dim], teven[dim];

ll a[dim];

void build(ll v, ll l, ll r){
    if(l == r){
        if(l % 2 != 0)
            todd[v] = a[l];
        else
            teven[v] = a[l];
        
        return;
    }
    
    ll mid = (l + r) >> 1;
    
    build(2 * v + 1, l, mid);
    build(2 * v + 2, mid + 1, r);
    
    todd[v] = (todd[2 * v + 1] xor todd[2 * v + 2]);
    teven[v] = (teven[2 * v + 1] xor teven[2 * v + 2]);
}

void update(ll v, ll l, ll r, ll pos, ll val){
    if(pos < l || pos > r)
        return;
    
    if(l == r){
        if(pos % 2 != 0)
            todd[v] = val;
        else
            teven[v] = val;
        
        return;
    }
    
    ll mid = (l + r) >> 1;
    
    update(2 * v + 1, l, mid, pos, val);
    update(2 * v + 2, mid + 1, r, pos, val);
    
    todd[v] = (todd[2 * v + 1] xor todd[2 * v + 2]);
    teven[v] = (teven[2 * v + 1] xor teven[2 * v + 2]);
}

ll query(ll v, ll l, ll r, ll ql, ll qr, bool ok){
    if(r < ql || qr < l)
        return 0;
    
    if(ql <= l && r <= qr){
        if(ok)
            return todd[v];
        return teven[v];
    }
    
    ll mid = (l + r) >> 1;
    
    return (query(2 * v + 1, l, mid, ql, qr, ok) xor query(2 * v + 2, mid + 1, r, ql, qr, ok));
}

int main(){
    ll n, q;
    cin >> n >> q;
    
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    
    build(1, 1, n);
    
    while(q--){
        ll type;
        cin >> type;
        
        if(type == 1){
            ll pos, val;
            cin >> pos >> val;
            
            a[pos] =  val;
            
            update(1, 1, n, pos, val);
        }
        else{
            ll l, r;
            cin >> l >> r;
            
            if((r - l + 1) % 2 == 0)
                cout << 0 << endl;
            else{
                if(l % 2 != 0){ // odd
                    cout << query(1, 1, n, l, r, true) << endl;
                }
                else{ // even
                    cout << query(1, 1, n, l, r, false) << endl;
                }
            }
        }
    }
     
    return 0;
}

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