oj.uz

답안 #451997

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
451997 2021-08-03T15:46:33 Z lukadupli XORanges (eJOI19_xoranges) C++14
0 / 100
 4 ms 460 KB 
#include <bits/stdc++.h>
 
#define f first
#define s second
 
using namespace std;
 
typedef pair <int, int> pii;
 
const int MAX = 1 << 13;
 
struct tournament
{
    pair <int, pii> nodes[2 * MAX];
 
    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){
        if(r - l == 1){
            if(l < arr_size) nodes[node] = {arr[l], {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], 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];
 
    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;
 
            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 Runtime error 4 ms 460 KB Execution killed with signal 11
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 -