Submission #969381

#	Time	Username	Problem	Language	Result	Execution time	Memory
969381		HasanV11010238	XORanges (eJOI19_xoranges)	C++17	100 / 100	449 ms	16720 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000000
struct SegTree{
    vector<int> ve, tr;
    SegTree(int n, vector<int> vec){
        ve = vec;
        tr.assign(4 * n + 1, -1);
        build(1, 0, n - 1);
    }
    void build(int v, int l, int r){
        if (l == r){
            tr[v - 1] = ve[l];
        }
        else{
            int mid = (l + r) / 2;
            build(v * 2, l, mid);
            build(v * 2 + 1, mid + 1, r);
            tr[v - 1] = (tr[v * 2 - 1]) ^ (tr[v * 2]);
        }
    }
    void update(int v, int l, int r, int po, int va){
        if (l == r){
            tr[v - 1] = va;
        }
        else{
            int mid = (l + r) / 2;
            if (po <= mid){
                update(v * 2, l, mid, po, va);
            }
            else{
                update(v * 2 + 1, mid + 1, r, po, va);
            }
            tr[v - 1] = (tr[v * 2 - 1]) ^ (tr[v * 2]);
        }
    }
    int query(int v, int l, int r, int ql, int qr){
        if (ql <= l && r <= qr){
            return tr[v - 1];
        }
        else if (r < ql || l > qr){
            return 0;
        }
        else{
            int mid = (l + r) / 2;
            return query(v * 2, l, mid, ql, qr) ^ query(v * 2 + 1, mid + 1, r, ql, qr);
        }
    }
};
int main(){
    int n, a, q, t, l, r;
    cin>>n>>q;
    vector<int> ve0(n , 0), ve1(n, 0);
    for (int i = 0; i < n; i++){
        cin>>a;
        if (i % 2 == 0){
            ve0[i] = a;
        }
        else{
            ve1[i] = a;
        }
    }
    SegTree tr0(n, ve0), tr1(n, ve1);
    for (int i = 0; i < q; i++){
        cin>>t>>l>>r;
        if (t == 1){
            l--;
            if (l % 2 == 0){
                tr0.update(1, 0, n - 1, l, r);
            }
            else{
                tr1.update(1, 0, n - 1, l, r);
            }
        }
        else{
            l--, r--;
            if ((r - l + 1) % 2 == 0){
                cout<<0<<"\n";
            }
            else{
                if (l % 2 == 0){
                    cout<<tr0.query(1, 0, n - 1, l, r)<<"\n";
                }
                else{
                    cout<<tr1.query(1, 0, n - 1, l, r)<<"\n";
                }
            }
        }
    }
}

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