Submission #452025

#	Time	Username	Problem	Language	Result	Execution time	Memory
452025		lukadupli	XORanges (eJOI19_xoranges)	C++14	0 / 100	59 ms	1348 KiB

xoranges

#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

typedef pair <int, int> pii;

const int MAX = 1 << 17;

int n, q, arr[MAX];
pair <int, pii> nodes[2 * MAX];

struct tournament
{
    pair <int, pii> merge_nodes(pair <int, pii> node1, int l1, int r1, pair <int, pii> node2, int l2, int r2){
        pair <int, pii> res;

        res.f = node1.f ^ node2.f;
        if(r2 - l2 == 1) res.f ^= node1.s.f;
        if(r1 - l1 == 1) res.f ^= node2.s.s;

        if(r1 - l1 == 1 && r2 - l2 == 1){
            res.s.f = node1.s.f;
            res.s.s = node2.s.s;
        }
        else if(r1 - l1 == 1){
            res.s.f = node1.s.f ^ node2.s.s;
            res.s.s = node2.s.f;
        }
        else if(r2 - l2 == 1){
            res.s.f = node1.s.f ^ node2.s.f;
            res.s.s = node1.s.s;
        }
        else{
            res.s.f = node1.s.f ^ node2.s.f;
            res.s.s = node1.s.s ^ node2.s.s;
        }

        return res;
    }

    void build(int* arr, int arr_size, int node = 1, int l = 0, int r = 2 * MAX){
        //cout << node << ' ' << l << ' ' << r << ' ' << n << ' ' << q << '\n';
        if(r - l == 1){
            nodes[node] = {arr[l], {arr[l], arr[l]}};
            return;
        }
        int m = (l + r) / 2;

        build(arr, arr_size, 2 * node, l, m);
        if(m < arr_size) build(arr, arr_size, 2 * node + 1, m, r);

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

    void change(int ind, int val, int node = 1, int l = 0, int r = 2 * MAX){
        if(r - l == 1){
            nodes[node] = {val, {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], l, m, nodes[2 * node + 1], m, r);
    }

    pair <pair <int, pii>, pii> query(int lq, int rq, int node = 1, int l = 0, int r = 2 * MAX){
        //cout << lq << ' ' << rq << ' ' << node << ' ' << l << ' ' << r << '\n';
        if(l >= lq && r <= rq) return {nodes[node], {l, r}};

        int m = (l + r) / 2;

        pair <pair <int, pii>, pii> res;
        if(!(l >= rq || m <= lq) && !(m >= rq || r <= lq)){
            pair <pair <int, pii>, pii> node1 = query(lq, rq, 2 * node, l, m);
            pair <pair <int, pii>, pii> node2 = query(lq, rq, 2 * node + 1, m, r);

            res.f = merge_nodes(node1.f, node1.s.f, node1.s.s, node2.f, node2.s.f, node2.s.s);
            res.s.f = node1.s.f;
            res.s.s = node2.s.s;
        }
        else if(!(l >= rq || m <= lq)) res = query(lq, rq, 2 * node, l, m);
        else res = query(lq, rq, 2 * node + 1, m, r);

        return res;
    }
};

tournament tour;

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

    //cout << n << ' ' << q << '\n';
    //for(int i = 0; i < n; i++) cout << arr[i] << ' ';

    tour.build(arr, n);

    //cout << n << ' ' << q << '\n';
    //for(int i = 0; i < n; i++) cout << arr[i] << ' ';

    //cout << q << '\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;

            cout << tour.query(l - 1, r).f.f << '\n';
        }
    }

    return 0;
}

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