oj.uz

Submission #839318

# Submission time Handle Problem Language Result Execution time Memory
839318 2023-08-29T16:37:08 Z raul2008487 XORanges (eJOI19_xoranges) C++17
100 / 100
 449 ms 10320 KB 
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
#define vl vector<ll>
//#define endl "\n"
using namespace std;
const int sz = 2e5+5;
const ll inf = 100000000000000005;
ll id[sz], a[sz], tree[4*sz];
void build(ll v, ll l, ll r){
    if(l==r){
        tree[v] = a[l];
        return ;
    }
    ll m = (l+r)>>1;
    build(v*2,l,m);
    build(v*2+1,m+1,r);
    tree[v] = (tree[v*2] ^ tree[v*2+1]);
}
void update(ll v, ll tl, ll tr, ll pos, ll val){
    if(tl > tr){return ;}
    if(tl == tr && tr == pos){
        tree[v] = val;
        a[tl] = val;
        return ;
    }
    ll tm = (tl+tr)>>1;
    if(pos <= tm){
        update(v*2,tl,tm,pos,val);
    }
    else{
        update(v*2+1,tm+1,tr,pos,val);
    }
    tree[v] = (tree[v*2] ^ tree[v*2+1]);
}
ll get(ll v, ll tl, ll tr, ll l, ll r){
    if(tl > r || tr < l){
        return 0;
    }
    if(tl >= l && tr <= r){
        return tree[v];
    }
    ll tm = (tl+tr)>>1;
    ll s1 = get(v*2,tl,tm,l,r);
    ll s2 = get(v*2+1,tm+1,tr,l,r);
    return (s1^s2);
}
int main(){
    ll n,q,i,j,cur=0,l,r,qt;
    cin>>n>>q;
    vl v(n+1);
    for(i=1;i<=n;i++){
        cin>>v[i];
    }
    for(i=1;i<=n;i+=2){
        id[i] = ++cur;
        a[cur] = v[i];
    }
    for(i=2;i<=n;i+=2){
        id[i] = ++cur;
        a[cur] = v[i];
    }
    build(1,1,n);
    while(q--){
        cin>>qt;
        if(qt == 1){
            cin>>l>>r;
            update(1,1,n,id[l],r);
        }
        else{
            cin>>l>>r;
            if((r-l+1) % 2 == 0){cout << 0 << endl;continue;}
            cout << get(1,1,n,id[l],id[r]) << endl;
        }
    }
}
/*
5 6
1 2 3 4 5
2 1 3
1 1 3
2 1 5
2 4 4
1 1 1
2 4 4
 
*/

Compilation message

xoranges.cpp: In function 'int main()':
xoranges.cpp:49:14: warning: unused variable 'j' [-Wunused-variable]
   49 |     ll n,q,i,j,cur=0,l,r,qt;
      |              ^

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 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 2 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 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 8 ms 468 KB Output is correct
12 Correct 7 ms 468 KB Output is correct
13 Correct 9 ms 596 KB Output is correct
14 Correct 9 ms 596 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 10320 KB Output is correct
2 Correct 416 ms 10184 KB Output is correct
3 Correct 449 ms 10184 KB Output is correct
4 Correct 393 ms 10216 KB Output is correct
5 Correct 400 ms 10320 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 2 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 8 ms 468 KB Output is correct
12 Correct 7 ms 468 KB Output is correct
13 Correct 9 ms 596 KB Output is correct
14 Correct 9 ms 596 KB Output is correct
15 Correct 431 ms 10320 KB Output is correct
16 Correct 416 ms 10184 KB Output is correct
17 Correct 449 ms 10184 KB Output is correct
18 Correct 393 ms 10216 KB Output is correct
19 Correct 400 ms 10320 KB Output is correct
20 Correct 326 ms 9620 KB Output is correct
21 Correct 320 ms 9676 KB Output is correct
22 Correct 321 ms 9688 KB Output is correct
23 Correct 397 ms 10180 KB Output is correct
24 Correct 388 ms 10160 KB Output is correct