oj.uz

Submission #929333

# Submission time Handle Problem Language Result Execution time Memory
929333 2024-02-18T04:58:36 Z hngr XORanges (eJOI19_xoranges) C++14
100 / 100
 471 ms 16208 KB 
//UDUUUU SHAAGD LLR CN INGEL DAWCIH YMN DEER SONIN PSDA WE;
#include <iostream>
#include <vector>
#include <set>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#define int long long 
using namespace std;
const int N = 2e5+7;
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 qry1(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 qry1(2*node+1, l, mid, L, R)^qry1(2*node+2, mid+1, r, L, R);
    }
}
int qry2(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 qry2(2*node+1, l, mid, L, R)^qry2(2*node+2, mid+1, r, L, R);
    }
}
 
int32_t main(){
    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 a, b;
            cin >> a >> b;
            a--;
            Update(0, 0, n-1, a, b);
        }
        else{
            int l, r;
            cin >> l >> r;
            r--; l--;
            int len=r-l+1;
            if(len&1){
                if(l&1){
                    cout << qry2(0, 0, n-1, l, r) << '\n';
                }
                else {
                    cout << qry1(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 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 2 ms 2500 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 9 ms 4700 KB Output is correct
12 Correct 9 ms 4700 KB Output is correct
13 Correct 10 ms 4700 KB Output is correct
14 Correct 11 ms 4696 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 13648 KB Output is correct
2 Correct 432 ms 15968 KB Output is correct
3 Correct 470 ms 15904 KB Output is correct
4 Correct 447 ms 15952 KB Output is correct
5 Correct 431 ms 16028 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 2 ms 2396 KB Output is correct
7 Correct 2 ms 2500 KB Output is correct
8 Correct 2 ms 2396 KB Output is correct
9 Correct 3 ms 2396 KB Output is correct
10 Correct 2 ms 2392 KB Output is correct
11 Correct 9 ms 4700 KB Output is correct
12 Correct 9 ms 4700 KB Output is correct
13 Correct 10 ms 4700 KB Output is correct
14 Correct 11 ms 4696 KB Output is correct
15 Correct 471 ms 13648 KB Output is correct
16 Correct 432 ms 15968 KB Output is correct
17 Correct 470 ms 15904 KB Output is correct
18 Correct 447 ms 15952 KB Output is correct
19 Correct 431 ms 16028 KB Output is correct
20 Correct 345 ms 15836 KB Output is correct
21 Correct 333 ms 15696 KB Output is correct
22 Correct 366 ms 15700 KB Output is correct
23 Correct 420 ms 15812 KB Output is correct
24 Correct 420 ms 16208 KB Output is correct