oj.uz

Submission #453190

# Submission time Handle Problem Language Result Execution time Memory
453190 2021-08-04T08:47:06 Z lukadupli XORanges (eJOI19_xoranges) C++14
55 / 100
 61 ms 2844 KB 
#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

typedef pair <int, int> pii;

const int MAX = 1 << 17;

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1308 KB Output is correct
2 Correct 2 ms 1304 KB Output is correct
3 Correct 3 ms 1228 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 3 ms 1228 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1228 KB Output is correct
2 Correct 5 ms 1228 KB Output is correct
3 Correct 4 ms 1228 KB Output is correct
4 Correct 4 ms 1228 KB Output is correct
5 Correct 4 ms 1228 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1308 KB Output is correct
2 Correct 2 ms 1304 KB Output is correct
3 Correct 3 ms 1228 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 3 ms 1228 KB Output is correct
6 Correct 4 ms 1228 KB Output is correct
7 Correct 5 ms 1228 KB Output is correct
8 Correct 4 ms 1228 KB Output is correct
9 Correct 4 ms 1228 KB Output is correct
10 Correct 4 ms 1228 KB Output is correct
11 Correct 14 ms 1528 KB Output is correct
12 Correct 14 ms 1484 KB Output is correct
13 Correct 17 ms 1524 KB Output is correct
14 Correct 18 ms 1524 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 2844 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1308 KB Output is correct
2 Correct 2 ms 1304 KB Output is correct
3 Correct 3 ms 1228 KB Output is correct
4 Correct 3 ms 1228 KB Output is correct
5 Correct 3 ms 1228 KB Output is correct
6 Correct 4 ms 1228 KB Output is correct
7 Correct 5 ms 1228 KB Output is correct
8 Correct 4 ms 1228 KB Output is correct
9 Correct 4 ms 1228 KB Output is correct
10 Correct 4 ms 1228 KB Output is correct
11 Correct 14 ms 1528 KB Output is correct
12 Correct 14 ms 1484 KB Output is correct
13 Correct 17 ms 1524 KB Output is correct
14 Correct 18 ms 1524 KB Output is correct
15 Runtime error 61 ms 2844 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -