oj.uz

Submission #810714

# Submission time Handle Problem Language Result Execution time Memory
810714 2023-08-06T14:29:25 Z AlphaMale06 XORanges (eJOI19_xoranges) C++14
100 / 100
 108 ms 11204 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 200010;
int a[N];
int st1[4*N];
int st2[4*N];
void Build(int node, int l, int r){
    if(l>r)return;
    if(l==r){
        if(l&1){
            st2[node]=a[l];
        }
        else{
            st1[node]=a[l];
        }
        return;
    }
    int mid=(l+r)/2;
    Build(2*node+1, l, mid);
    Build(2*node+2, mid+1, r);
    st1[node]=st1[2*node+1]^st1[2*node+2];
    st2[node]=st2[2*node+1]^st2[2*node+2];
}
void Update(int node, int l, int r, int ind, int val){
    if(l>r || l>ind || r<ind)return;
    if(l==r){
        if(l&1){
            st2[node]=val;
        }
        else st1[node]=val;
        return;
    }
    else{
        int mid=(l+r)/2;
        Update(2*node+1, l, mid, ind, val);
        Update(2*node+2, mid+1, r, ind, val);
    }
    st2[node]=st2[2*node+1]^st2[2*node+2];
    st1[node]=st1[2*node+1]^st1[2*node+2];
}

int get1(int node, int l, int r, int L, int R){
    if(l>R || r<L || l>r){
        return 0;
    }
    else if(l>=L && r<=R){
        return st1[node];
    }
    else{
        int mid=(l+r)/2;
        return get1(2*node+1, l, mid, L, R)^get1(2*node+2, mid+1, r, L, R);
    }
}
int get2(int node, int l, int r, int L, int R){
    if(l>R || r<L || l>r){
        return 0;
    }
    else if(l>=L && r<=R){
        return st2[node];
    }
    else{
        int mid=(l+r)/2;
        return get2(2*node+1, l, mid, L, R)^get2(2*node+2, mid+1, r, L, R);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, q;
    cin >> n >> q;
    for(int i=0; i< n; i++){
        cin >> a[i];
    }
    Build(0, 0, n-1);
    while(q--){
        int t;
        cin >> t;
        if(t==1){
            int ind, val;
            cin >> ind >> val;
            ind--;
            Update(0, 0, n-1, ind, val);
        }
        else{
            int l, r;
            cin >> l >> r;
            r--; l--;
            int len=r-l+1;
            if(len&1){
                if(l&1){
                    cout << get2(0, 0, n-1, l, r) << '\n';
                }
                else {
                    cout << get1(0, 0, n-1, l, r) << '\n';
                }
            }
            else{
                cout << 0 << '\n';
            }
        }
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 11184 KB Output is correct
2 Correct 106 ms 11204 KB Output is correct
3 Correct 102 ms 11148 KB Output is correct
4 Correct 90 ms 10868 KB Output is correct
5 Correct 94 ms 10872 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 3 ms 596 KB Output is correct
15 Correct 108 ms 11184 KB Output is correct
16 Correct 106 ms 11204 KB Output is correct
17 Correct 102 ms 11148 KB Output is correct
18 Correct 90 ms 10868 KB Output is correct
19 Correct 94 ms 10872 KB Output is correct
20 Correct 98 ms 10876 KB Output is correct
21 Correct 98 ms 10972 KB Output is correct
22 Correct 99 ms 10880 KB Output is correct
23 Correct 92 ms 10828 KB Output is correct
24 Correct 94 ms 10824 KB Output is correct