oj.uz

Submission #978055

# Submission time Handle Problem Language Result Execution time Memory
978055 2024-05-08T17:51:54 Z SeenSiravit XORanges (eJOI19_xoranges) C++14
100 / 100
 103 ms 9416 KB 
#include<bits/stdc++.h>
#define ll long long
 
using namespace std;
 
const int mxN = 2e5 + 5;
 
void build(int l,int r,int node,vector<int>& arr , vector<int>& seg){
    if(l == r){
        seg[node] = arr[l];
        return ;
    }
 
    int mid = (l + r) / 2;
 
    build(l,mid, node*2 , arr , seg);
    build(mid+1,r , node*2 + 1 , arr , seg);
 
    seg[node] = seg[node*2] ^ seg[node*2 + 1];
}
 
void update(int l,int r, int idx , int val , int node , vector<int>& arr , vector<int>& seg){
    if(l>idx || r<idx) return ;
 
    if(l == r){
        arr[idx] = val;
        seg[node] = val;
        return ;
    }
 
    int mid = (l + r) / 2;
 
    update(l,mid , idx,val , node*2 , arr , seg);
    update(mid+1,r, idx,val , node*2 + 1 , arr , seg);
 
    seg[node] = seg[node*2] ^ seg[node*2 + 1];
}
 
int query(int l,int r, int curr_l , int curr_r , int node ,vector<int>& seg){
    if(curr_l>r || curr_r<l) return 0;
    if(l<=curr_l && curr_r<=r) return seg[node];
 
    int mid = (curr_l + curr_r) / 2;
 
    return query(l,r,curr_l,mid , node*2 ,seg) ^ query(l,r,mid+1,curr_r,node*2 + 1  , seg);
}
 
int main(){
    ios::sync_with_stdio(0),cin.tie(0);
 
    int n,q;
    
    cin>> n >> q;
 
    vector<int> a(n+1 , 0) , b(n+1 , 0);
    for(int i=1;i<=n;i++){
        if(i%2 == 1) cin>> a[i];
        else cin>> b[i];
    }
 
    vector<int> segA(n*4 , 0) , segB(n*4 , 0);
    build(1,n,1,a,segA);
    build(1,n,1,b,segB);
 
    while(q--){
        int cmd;
        cin>> cmd;
 
        if(cmd == 1){
            int idx,val;
            cin>> idx >> val;
 
            if(idx%2 == 1) update(1,n,idx,val,1,a,segA);
            else update(1,n,idx,val,1,b,segB);
        }else{
            int l,r;
            cin>> l >> r;
 
            int len = r-l+1;
 
            if(len % 2 == 0) cout<< 0 << "\n";
            else{
                if(l%2 == 1) cout<< query(l,r,1,n,1,segA) << "\n";
                else cout<< query(l,r,1,n,1,segB) << "\n";
            }
        }
    }
 
 
    return 0;
}

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 348 KB Output is correct
4 Correct 0 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 348 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 348 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 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 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 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 3 ms 600 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 604 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 9416 KB Output is correct
2 Correct 102 ms 9300 KB Output is correct
3 Correct 95 ms 9304 KB Output is correct
4 Correct 92 ms 9296 KB Output is correct
5 Correct 90 ms 9300 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 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 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 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 3 ms 600 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 96 ms 9416 KB Output is correct
16 Correct 102 ms 9300 KB Output is correct
17 Correct 95 ms 9304 KB Output is correct
18 Correct 92 ms 9296 KB Output is correct
19 Correct 90 ms 9300 KB Output is correct
20 Correct 99 ms 8788 KB Output is correct
21 Correct 96 ms 8788 KB Output is correct
22 Correct 103 ms 9116 KB Output is correct
23 Correct 87 ms 9296 KB Output is correct
24 Correct 92 ms 9296 KB Output is correct