oj.uz

Submission #1096252

# Submission time Handle Problem Language Result Execution time Memory
1096252 2024-10-04T07:05:42 Z RED1 XORanges (eJOI19_xoranges) C++14
100 / 100
 119 ms 16216 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define Algerian ios::sync_with_stdio(false);
#define OI cin.tie(NULL);
 
struct segtree {
    int size;
    vector<ll> evals;
 
    void init(int n){
        size = 1;
        while(size<n) size *= 2;
        evals.assign(2*size, 0LL);
    }
 
    void build(vector<int> &a, int x, int lx, int rx){
        if(rx-lx==1){
            if(lx < (int)a.size()) evals[x] = a[lx];
            return;
        }
        int m = (lx+rx)/2;
        build(a,2*x+1,lx,m);
        build(a,2*x+2,m,rx);
        evals[x]=evals[2*x+1]^evals[2*x+2];
    }
 
    void build(vector<int> &a){
        build(a,0,0,size);
    }
 
    void set(int i, int v, int x, int lx, int rx){
        if(rx-lx==1){
            evals[x]=v;
            return;
        }
        int m = (lx+rx)/2;
        if(i<m) set(i,v,2*x+1,lx,m);
        else set(i,v,2*x+2,m,rx);
 
        evals[x]=evals[2*x+1]^evals[2*x+2];
    }
 
    void set(int i, int v){
        set(i,v,0,0,size);
    }
 
    ll eval(int l, int r, int x, int lx, int rx){
        if(lx>=r ||l>=rx) return 0;
        if(lx>=l && rx<=r) return evals[x];
        int m = (lx+rx)/2;
        ll s1 = eval(l,r,2*x+1,lx,m);
        ll s2 = eval(l,r,2*x+2,m,rx);
        return s1^s2;
    }
 
    ll eval(int l, int r){
        return eval(l,r,0,0,size);
    }
};
 
int main (){
    Algerian OI
 
    int n,q;
    cin >> n >> q;
    vector<int> arr1(n,0),arr2(n,0);
    for (int i = 0; i < n; ++i){
        if(i%2==0) cin >> arr1[i];
        else cin >> arr2[i];
    }
    
 
    segtree st1,st2;
    st1.init(n);
    st2.init(n);
    st1.build(arr1);
    st2.build(arr2);
    while(q--){
        int op; cin >> op;
        if(op==1){
            int i,v;
            cin >> i >> v;
            --i;
            if(i%2==0) st1.set(i,v);
            else st2.set(i,v);
        }
        else{
            int l,r; cin >> l >> r;
            if((r-l+1)%2==0) cout << 0 << '\n';
            else{
                --l;
                if(l%2==0) cout << st1.eval(l,r) << '\n';
                else cout  << st2.eval(l,r) << '\n';
            }
        }
    }
    
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 4 ms 860 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 856 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 16212 KB Output is correct
2 Correct 102 ms 16212 KB Output is correct
3 Correct 98 ms 16216 KB Output is correct
4 Correct 83 ms 15708 KB Output is correct
5 Correct 92 ms 15716 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 452 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 4 ms 860 KB Output is correct
13 Correct 2 ms 724 KB Output is correct
14 Correct 2 ms 856 KB Output is correct
15 Correct 91 ms 16212 KB Output is correct
16 Correct 102 ms 16212 KB Output is correct
17 Correct 98 ms 16216 KB Output is correct
18 Correct 83 ms 15708 KB Output is correct
19 Correct 92 ms 15716 KB Output is correct
20 Correct 90 ms 15952 KB Output is correct
21 Correct 89 ms 15844 KB Output is correct
22 Correct 81 ms 15976 KB Output is correct
23 Correct 119 ms 15696 KB Output is correct
24 Correct 75 ms 15760 KB Output is correct