oj.uz

Submission #747804

# Submission time Handle Problem Language Result Execution time Memory
747804 2023-05-24T18:59:28 Z Elvin_Fritl XORanges (eJOI19_xoranges) C++17
100 / 100
 375 ms 11232 KB 
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")

#include <bits/stdc++.h>

using namespace std;

vector<int> tree[2];

void build(int in, int v, vector<int> &V, int l, int r) {
    if (l == r) {
        tree[in][v] = V[l];
        return;
    }
    int m = (l + r) / 2;
    build(in, 2 * v, V, l, m);
    build(in, 2 * v + 1, V, m + 1, r);
    tree[in][v] = tree[in][2 * v] ^ tree[in][2 * v + 1];
}

void update(int in, int v, int l, int r, int pos, int val) {
    if (l == r) {
        tree[in][v] = val;
        return;
    }
    int m = (l + r) / 2;
    if (pos <= m) {
        update(in, 2 * v, l, m, pos, val);
    } else {
        update(in, 2 * v + 1, m + 1, r, pos, val);
    }
    tree[in][v] = tree[in][2 * v] ^ tree[in][2 * v + 1];
}

int xor_answer(int in, int v, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return tree[in][v];
    }
    int m = (l + r) / 2;
    int ll = 0, rr = 0;
    if (ql <= m) {
        ll = xor_answer(in, 2 * v, l, m, ql, qr);
    }
    if (qr > m) {
        rr = xor_answer(in, 2 * v + 1, m + 1, r, ql, qr);
    }
    return ll ^ rr;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N, Q;
    cin>>N>>Q;
    vector<int> V(N);
    for(int i=0;i<N;i++) {
        cin>>V[i];
    }
    vector<int> A,B;
    for(int i=0;i<N;i++) {
        if(i%2==0){
            A.push_back(V[i]);
        }
        else{
            B.push_back(V[i]);
        }
    }
    tree[0].resize(4 * A.size());
    tree[1].resize(4 * B.size());
    build(0,1,A,0,A.size()-1);
    build(1,1,B,0,B.size()-1);

    for(int i=0;i<Q;i++) {
        int op,l,r;
        cin>>op>>l>>r;
        l--;
        r--;
        int sz = 0;
        if(l%2==0){
            sz=A.size()-1;
        }
        else{
            sz=B.size()-1;
        }
        if (op==1){
            update(l % 2, 1, 0, sz, l / 2, r + 1);
        }
        else{
            if((r-l+1)%2==0){
                cout<<0<<endl;
                continue;
            }
            cout<<xor_answer(l % 2, 1, 0, sz, l / 2, r / 2)<<endl;
        }
    }
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 6 ms 596 KB Output is correct
12 Correct 6 ms 584 KB Output is correct
13 Correct 9 ms 592 KB Output is correct
14 Correct 10 ms 604 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 369 ms 11232 KB Output is correct
2 Correct 375 ms 11196 KB Output is correct
3 Correct 359 ms 11200 KB Output is correct
4 Correct 336 ms 10816 KB Output is correct
5 Correct 324 ms 10904 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 316 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 6 ms 596 KB Output is correct
12 Correct 6 ms 584 KB Output is correct
13 Correct 9 ms 592 KB Output is correct
14 Correct 10 ms 604 KB Output is correct
15 Correct 369 ms 11232 KB Output is correct
16 Correct 375 ms 11196 KB Output is correct
17 Correct 359 ms 11200 KB Output is correct
18 Correct 336 ms 10816 KB Output is correct
19 Correct 324 ms 10904 KB Output is correct
20 Correct 228 ms 11108 KB Output is correct
21 Correct 226 ms 10936 KB Output is correct
22 Correct 228 ms 10996 KB Output is correct
23 Correct 338 ms 10888 KB Output is correct
24 Correct 332 ms 10948 KB Output is correct