oj.uz

답안 #452018

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
452018 2021-08-03T16:09:21 Z lukadupli XORanges (eJOI19_xoranges) C++14
0 / 100
 1000 ms 6356 KB 
#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

typedef pair <int, int> pii;

const int MAX = 1 << 17;

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';
        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;
    }
};

int n, q, arr[MAX];
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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1082 ms 6356 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 460 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -