Submission #1219180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219180		giorgi123glm	XORanges (eJOI19_xoranges)	C++20	100 / 100	105 ms	9800 KiB

xoranges

#include <functional>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define int long long

template <typename T>
class segment_tree {
    public:
        int siz = 1;
        vector <T> segtree;
        function <T(T, T)> merge;
        
        segment_tree(function <T(T, T)> IN) : merge (IN) {}

        void resize (int n) {
            while (siz < n)
                siz *= 2;
            segtree.resize (2 * siz);
        }

        void update (int ind, T K) {
            int u = siz + ind - 1;
            segtree[u] = K;
            u /= 2;
            while (u)
                segtree[u] = merge (
                    segtree[2 * u], segtree[2 * u + 1]
                ), u /= 2;
        }

        T get (int L, int R, int u, int l, int r) {
            if (r < L || R < l)
                return 0;

            if (L <= l && r <= R)
                return segtree[u];

            const int m = (l + r) / 2;
            return merge (
                get (L, R, 2 * u, l, m),
                get (L, R, 2 * u + 1, m + 1, r)
            );
        }

        T get (int L, int R) {
            return get (L, R, 1, 1, siz);
        }
};

signed main () {
    ios::sync_with_stdio (false);
    cin.tie (0);
    cout.tie (0);

    int N = 0, Q = 0;
    cin >> N >> Q;

    vector <segment_tree <int> > segtree (
        2,
        segment_tree <int> (
            [](int a, int b) {
                return (a xor b);
            }
        )
    );
    segtree[0].resize (N + 100);
    segtree[1].resize (N + 100);

    for (int i = 1; i <= N; i++) {
        int t = 0;
        cin >> t;

        segtree[i % 2].update (i, t);
    }

    while (Q--) {
        int t = 0;
        cin >> t;

        if (t == 1) {
            int a = 0, b = 0;
            cin >> a >> b;

            segtree[a % 2].update (a, b);
        } else {
            int l = 0, r = 0;
            cin >> l >> r;

            if ((r - l + 1) % 2 == 0)
                cout << 0 << '\n';
            else
                cout << segtree[r % 2].get (l, r) << '\n';
        }
    }
}

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