oj.uz

Submission #650852

# Submission time Handle Problem Language Result Execution time Memory
650852 2022-10-15T19:30:06 Z edogawa_something XORanges (eJOI19_xoranges) C++17
100 / 100
 438 ms 12236 KB 
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef string st;
typedef bool bl;
typedef vector<ll> vii;
typedef pair<ll,ll> pii;
typedef vector<pii> vpi;
#define pu push
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define fast ios_base::sync_with_stdio(0);cin.tie();
#define test ll qqqqq;cin>>qqqqq;while(qqqqq--)
#define F first
#define S second
#define forn(i,n) for(ll i=0;i<n;i++)
#define forx(i,j,n) for(ll i=j;i<n;i++)
#define pb push_back
#define pob pop_back
#define all(v) v.begin(),v.end()
#define lb lower_bound
#define ub upper_bound
#define pof pop_front
const ll dx[]{1,0,-1,0};
const ll dy[]{0,1,0,-1};
const ll inf=2e18;
const ll mod=1e9+7;
const ll M=1e6+1;
const ll MM=10002;
const ll MMM=101;
const ld pi=acos(-1);
const ll mod1=1000000321;
ll n,q,a[M];
struct seg{
    ll sz=1;
    vii xors;
    void init(ll x){
        while(sz<x)
        sz=(sz<<1);
        xors.resize((sz<<1));
    }
    void up(ll i,ll v,ll x,ll lx,ll rx){
        if(rx-lx==1){
            xors[x]=v;
            return;
        }
        ll mid=((lx+rx)>>1);
        if(i<mid)
        up(i,v,x*2+1,lx,mid);
        else
        up(i,v,x*2+2,mid,rx);
        xors[x]=(xors[x*2+1]^xors[x*2+2]);
    }
    ll query(ll l,ll r,ll x,ll lx,ll rx){
        if(lx>=l&&rx<=r)
        return xors[x];
        if(lx>=r||rx<=l)
        return 0;
        ll mid=((lx+rx)>>1);
        return (query(l,r,x*2+1,lx,mid)^query(l,r,x*2+2,mid,rx));
    }
};
seg s0,s1;
ll solve(ll l,ll r){
   if(!((r-l)&1))
   return 0;
   if((l&1))
   return s1.query(l,r,0,0,s1.sz);
   else
   return s0.query(l,r,0,0,s1.sz);
}
int main(){
    fast
    cin>>n>>q;
    s0.init(n),s1.init(n);
    forn(i,n){
        ll x;
        cin>>x;
        if((i&1))
        s1.up(i,x,0,0,s1.sz);
        else
        s0.up(i,x,0,0,s1.sz);
    }
    while(q--){
        ll ty,l,r;
        cin>>ty>>l>>r;
        if(ty==2)
        cout<<solve(l-1,r)<<'\n';
        else{
            l--;
            if((l&1))
            s1.up(l,r,0,0,s1.sz);
            else
            s0.up(l,r,0,0,s1.sz);
        }
    }
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 328 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 2 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 1 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 328 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 7 ms 724 KB Output is correct
12 Correct 7 ms 724 KB Output is correct
13 Correct 13 ms 724 KB Output is correct
14 Correct 14 ms 740 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 10760 KB Output is correct
2 Correct 401 ms 10300 KB Output is correct
3 Correct 402 ms 10240 KB Output is correct
4 Correct 438 ms 10144 KB Output is correct
5 Correct 370 ms 10324 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 1 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 328 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 7 ms 724 KB Output is correct
12 Correct 7 ms 724 KB Output is correct
13 Correct 13 ms 724 KB Output is correct
14 Correct 14 ms 740 KB Output is correct
15 Correct 415 ms 10760 KB Output is correct
16 Correct 401 ms 10300 KB Output is correct
17 Correct 402 ms 10240 KB Output is correct
18 Correct 438 ms 10144 KB Output is correct
19 Correct 370 ms 10324 KB Output is correct
20 Correct 282 ms 11676 KB Output is correct
21 Correct 279 ms 11636 KB Output is correct
22 Correct 309 ms 11672 KB Output is correct
23 Correct 403 ms 12236 KB Output is correct
24 Correct 380 ms 12012 KB Output is correct