Submission #1096252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096252		RED1	XORanges (eJOI19_xoranges)	C++14	100 / 100	119 ms	16216 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Algerian ios::sync_with_stdio(false);
#define OI cin.tie(NULL);
 
struct segtree {
    int size;
    vector<ll> evals;
 
    void init(int n){
        size = 1;
        while(size<n) size *= 2;
        evals.assign(2*size, 0LL);
    }
 
    void build(vector<int> &a, int x, int lx, int rx){
        if(rx-lx==1){
            if(lx < (int)a.size()) evals[x] = a[lx];
            return;
        }
        int m = (lx+rx)/2;
        build(a,2*x+1,lx,m);
        build(a,2*x+2,m,rx);
        evals[x]=evals[2*x+1]^evals[2*x+2];
    }
 
    void build(vector<int> &a){
        build(a,0,0,size);
    }
 
    void set(int i, int v, int x, int lx, int rx){
        if(rx-lx==1){
            evals[x]=v;
            return;
        }
        int m = (lx+rx)/2;
        if(i<m) set(i,v,2*x+1,lx,m);
        else set(i,v,2*x+2,m,rx);
 
        evals[x]=evals[2*x+1]^evals[2*x+2];
    }
 
    void set(int i, int v){
        set(i,v,0,0,size);
    }
 
    ll eval(int l, int r, int x, int lx, int rx){
        if(lx>=r ||l>=rx) return 0;
        if(lx>=l && rx<=r) return evals[x];
        int m = (lx+rx)/2;
        ll s1 = eval(l,r,2*x+1,lx,m);
        ll s2 = eval(l,r,2*x+2,m,rx);
        return s1^s2;
    }
 
    ll eval(int l, int r){
        return eval(l,r,0,0,size);
    }
};
 
int main (){
    Algerian OI
 
    int n,q;
    cin >> n >> q;
    vector<int> arr1(n,0),arr2(n,0);
    for (int i = 0; i < n; ++i){
        if(i%2==0) cin >> arr1[i];
        else cin >> arr2[i];
    }
    
 
    segtree st1,st2;
    st1.init(n);
    st2.init(n);
    st1.build(arr1);
    st2.build(arr2);
    while(q--){
        int op; cin >> op;
        if(op==1){
            int i,v;
            cin >> i >> v;
            --i;
            if(i%2==0) st1.set(i,v);
            else st2.set(i,v);
        }
        else{
            int l,r; cin >> l >> r;
            if((r-l+1)%2==0) cout << 0 << '\n';
            else{
                --l;
                if(l%2==0) cout << st1.eval(l,r) << '\n';
                else cout  << st2.eval(l,r) << '\n';
            }
        }
    }
    
}

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