Submission #1096623

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096623		Ariadna	XORanges (eJOI19_xoranges)	C++14	100 / 100	382 ms	13400 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

struct Segtree {
    int n, d;
    vector<int> st;
    
    Segtree(const vector<int>& a, int c) {
        n = (int)a.size();
        st = vector<int>(4*n);
        d = c;
        build(1, 0, n-1, a);
    }

    void build(int p, int l, int r, const vector<int>& a) {
        if (l == r) {
            if (l%2 == d) st[p] = a[l];
            else st[p] = 0; 
        } else {
            int m = (l+r)/2;
            build(2*p, l, m, a);
            build(2*p+1, m+1, r, a);
            st[p] = st[2*p]^st[2*p+1];
        }
    } 

    void change(int p, int l, int r, int i, int x) {
        if (l == r) {
            if (l%2 == d) st[p] = x;
            else st[p] = 0;
        } else {
            int m = (l+r)/2;
            if (i <= m) change(2*p, l, m, i, x);
            else change(2*p+1, m+1, r, i, x);
            st[p] = st[2*p]^st[2*p+1];
        }
    }

    int Xor(int p, int l, int r, int i, int j) {
        if (i > j) return 0;
        if (i == l && j == r) return st[p];
        int m = (l+r)/2;
        return Xor(2*p, l, m, i, min(m, j))^Xor(2*p+1, m+1, r, max(i, m+1), j);
    }

    void change(int i, int x) { change(1, 0, n-1, i, x); }
    int Xor(int i, int j) { return Xor(1, 0, n-1, i, j); }
};

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    Segtree St0(a, 0), St1(a, 1);

    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int p, x; cin >> p >> x;
            --p;
            if (p%2) St1.change(p, x);
            else St0.change(p, x);
        } else {
            int l, r; cin >> l >> r; --l; --r;
            if ((r-l+1)%2) {
                if (l%2) cout << St1.Xor(l, r) << endl;
                else cout << St0.Xor(l, r) << endl;
            } else cout << 0 << endl;
        }
    }

    return 0;
}

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