oj.uz

Submission #1109473

# Submission time Handle Problem Language Result Execution time Memory
1109473 2024-11-06T19:42:17 Z Irate XORanges (eJOI19_xoranges) C++17
100 / 100
 108 ms 13392 KB 
#include<bits/stdc++.h>
using namespace std;
struct Node{
    int odd = 0, even = 0;
};
struct SegmentTree{
    vector<Node>sTree;
    SegmentTree(int n){
        sTree.resize(4 * n);
    }
    Node Merge(Node &left, Node &right){
        Node res = {left.odd ^ right.odd, left.even ^ right.even};
        return res;
    }
    void Build(int node, int l, int r, vector<int>&v){
        if(l == r){
            if(l & 1)sTree[node] = {v[l], 0};
            else sTree[node] = {0, v[l]};
        }
        else{
            int mid = (l + r) >> 1;
            Build(node * 2, l, mid, v);
            Build(node * 2 + 1, mid + 1, r, v);
            sTree[node] = Merge(sTree[node * 2], sTree[node * 2 + 1]);
        }
    }
    void Update(int node, int l, int r, int pos, int val){
        if(l == r){
            if(l & 1)sTree[node] = {val, 0};
            else sTree[node] = {0, val};
        }
        else{
            int mid = (l + r) >> 1;
            if(pos <= mid){
                Update(node * 2, l, mid, pos, val);
            }
            else{
                Update(node * 2 + 1, mid + 1, r, pos, val);
            }
            sTree[node] = Merge(sTree[node * 2], sTree[node * 2 + 1]);
        }
    }
    Node Query(int node, int l, int r, int ql, int qr){
        if(ql <= l && r <= qr){
            return sTree[node];
        }
        if(ql > r || l > qr){
            Node ide;
            return ide;
        }
        int mid = (l + r) >> 1;
        Node lc = Query(node * 2, l, mid, ql, qr);
        Node rc = Query(node * 2 + 1, mid + 1, r, ql, qr);
        return Merge(lc, rc);
    }
};
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q;
    cin >> n >> q;
    vector<int>v(n + 1);
    for(int i = 1;i <= n;++i){
        cin >> v[i];
    }
    SegmentTree tree(n);
    tree.Build(1, 1, n, v);
    while(q--){
        int type;
        cin >> type;
        if(type == 1){
            int pos, val;
            cin >> pos >> val;
            tree.Update(1, 1, n, pos, val);
        }
        else{
            int l, r;
            cin >> l >> r;
            if(l % 2 != r % 2){
                cout << 0 << '\n';
            }
            else{
                Node res = tree.Query(1, 1, n, l, r);
                if(l % 2)cout << res.odd << '\n';
                else cout << res.even << '\n';
            }
        }
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 524 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 3 ms 740 KB Output is correct
12 Correct 3 ms 592 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 3 ms 592 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 13392 KB Output is correct
2 Correct 87 ms 13384 KB Output is correct
3 Correct 87 ms 13320 KB Output is correct
4 Correct 86 ms 13076 KB Output is correct
5 Correct 76 ms 13128 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 524 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 464 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 3 ms 740 KB Output is correct
12 Correct 3 ms 592 KB Output is correct
13 Correct 3 ms 592 KB Output is correct
14 Correct 3 ms 592 KB Output is correct
15 Correct 87 ms 13392 KB Output is correct
16 Correct 87 ms 13384 KB Output is correct
17 Correct 87 ms 13320 KB Output is correct
18 Correct 86 ms 13076 KB Output is correct
19 Correct 76 ms 13128 KB Output is correct
20 Correct 88 ms 13128 KB Output is correct
21 Correct 84 ms 13184 KB Output is correct
22 Correct 85 ms 13128 KB Output is correct
23 Correct 86 ms 13188 KB Output is correct
24 Correct 108 ms 13128 KB Output is correct