Submission #453191

#	Time	Username	Problem	Language	Result	Execution time	Memory
453191		lukadupli	XORanges (eJOI19_xoranges)	C++14	100 / 100	679 ms	10724 KiB

xoranges

#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

typedef pair <int, int> pii;

const int MAX = 1 << 18;

struct tournament
{
    pii nodes[2 * MAX];

    pii merge_nodes(pii l_node, int l_node_size, pii r_node, int r_node_size){
        pii res = {l_node.f, 0};

        if(l_node_size > 1) res.s = l_node.s;

        if((l_node_size) % 2){
            if(r_node_size > 1) res.f ^= r_node.s;
            res.s ^= r_node.f;
        }
        else{
            res.f ^= r_node.f;
            if(r_node_size) res.s ^= r_node.s;
        }

        return res;
    }

    void build(int *arr, int arr_size, int node = 1, int l = 0, int r = MAX){
        if(r - l == 1){
            if(l < arr_size) nodes[node] = {arr[l], arr[l]};
            return;
        }

        int m = (l + r) / 2;
        build(arr, arr_size, 2 * node, l, m);
        build(arr, arr_size, 2 * node + 1, m, r);

        nodes[node] = merge_nodes(nodes[2 * node], m - l, nodes[2 * node + 1], r - m);
    }

    void change(int ind, int val, int node = 1, int l = 0, int r = MAX){
        if(r - l == 1){
            nodes[node] = {val, val};
            return;
        }

        int m = (l + r) / 2;
        if(ind < m) change(ind, val, 2 * node, l, m);
        else change(ind, val, 2 * node + 1, m, r);

        nodes[node] = merge_nodes(nodes[2 * node], m - l, nodes[2 * node + 1], r - m);
    }

    pair <pii, int> query(int lq, int rq, int node = 1, int l = 0, int r = MAX){
        if(l >= lq && r <= rq) return {nodes[node], r - l};
        if(l >= rq || r <= lq) return {{0, 0}, 0};

        int m = (l + r) / 2;
        pair <pii, int> l_child = query(lq, rq, 2 * node, l, m);
        pair <pii, int> r_child = query(lq, rq, 2 * node + 1, m, r);

        return {merge_nodes(l_child.f, l_child.s, r_child.f, r_child.s), l_child.s + r_child.s};
    }


};

int n, q, arr[MAX];
tournament tour;

int main()
{
    cin >> n >> q;
    for(int i = 0; i < n; i++) cin >> arr[i];

    tour.build(arr, n);

    while(q--){
        int mode;
        cin >> mode;

        if(mode == 1){
            int ind, val;
            cin >> ind >> val;

            tour.change(ind - 1, val);
        }
        else{
            int l, r;
            cin >> l >> r;

            if((r - l + 1) % 2) cout << tour.query(l - 1, r).f.f << '\n';
            else cout << 0 << '\n';
        }
    }

    return 0;
}

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