oj.uz

Submission #1118049

# Submission time Handle Problem Language Result Execution time Memory
1118049 2024-11-24T19:25:43 Z boris_7 XORanges (eJOI19_xoranges) C++17
100 / 100
 411 ms 16200 KB 
#include<bits/stdc++.h>

using namespace std;
using ll = long long;


void update(ll l,ll r,ll u,ll ind,ll val,vector<ll>&seg){
    if(l==r && l==ind){
        seg[u]=val;
        return;
    }
    ll mid=(l+r)/2;
    if(ind<=mid) update(l,mid,u*2+1,ind,val,seg);
    else       update(mid+1,r,u*2+2,ind,val,seg);
    seg[u]=seg[u*2+1]^seg[u*2+2];
}

ll get(ll l,ll r,ll u,ll lx,ll rx,vector<ll>&seg){
    if(l>=lx && r<=rx){
        return seg[u];
    }
    if(l>rx||r<lx){
        return 0;
    }
    ll mid = (l+r)/2;
    return get(l,mid,u*2+1,lx,rx,seg)^get(mid+1,r,u*2+2,lx,rx,seg);
}

void solve(){
    ll n,q;
    cin>>n>>q;
    vector<ll>segk,segz;
    ll s = 1;
    while(s<=n) s*=2;
    segk = segz = vector<ll>(s*2);
    vector<ll>v(n);
    for(ll i = 0;i<n;i++){
        cin>>v[i];
        if(i%2==0) update(0,s-1,0,i,v[i],segz);
        else       update(0,s-1,0,i,v[i],segk);
    }
    while(q--){
        ll type;
        cin>>type;
        if(type==1){
            ll ind,x;
            cin>>ind>>x;
            --ind;
            if(ind%2==0) update(0,s-1,0,ind,x,segz);
            else         update(0,s-1,0,ind,x,segk);
        }
        else{
            ll l,r;
            cin>>l>>r;
            --l,--r;
            
            if     (l%2==0 && (r-l+1)%2==1) cout<<get(0,s-1,0,l,r,segz)<<endl;
            else if(l%2==1 && (r-l+1)%2==1) cout<<get(0,s-1,0,l,r,segk)<<endl;
            else if((r-l+1)%2==0) cout<<0<<endl;
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    // ll t;cin>>t;while(t--)
        solve();
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 7 ms 848 KB Output is correct
12 Correct 8 ms 848 KB Output is correct
13 Correct 9 ms 848 KB Output is correct
14 Correct 10 ms 848 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 408 ms 16200 KB Output is correct
2 Correct 411 ms 16172 KB Output is correct
3 Correct 400 ms 16112 KB Output is correct
4 Correct 400 ms 15944 KB Output is correct
5 Correct 375 ms 15944 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 504 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 2 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 7 ms 848 KB Output is correct
12 Correct 8 ms 848 KB Output is correct
13 Correct 9 ms 848 KB Output is correct
14 Correct 10 ms 848 KB Output is correct
15 Correct 408 ms 16200 KB Output is correct
16 Correct 411 ms 16172 KB Output is correct
17 Correct 400 ms 16112 KB Output is correct
18 Correct 400 ms 15944 KB Output is correct
19 Correct 375 ms 15944 KB Output is correct
20 Correct 271 ms 15980 KB Output is correct
21 Correct 284 ms 15976 KB Output is correct
22 Correct 289 ms 15944 KB Output is correct
23 Correct 374 ms 15696 KB Output is correct
24 Correct 380 ms 15780 KB Output is correct