Submission #1126830

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126830		Choco	XORanges (eJOI19_xoranges)	C++20	0 / 100	489 ms	24592 KiB

xoranges

#include<bits/stdc++.h>
using namespace std;
#define Study ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define ff first 
#define ss second
#define ins insert
#define all(x) x.begin(),x.end()
#define fori(x,y,z) for(ll x=y;x<=z;x++)
const ll INF=1e9;
const ll sz=2e5+10;
const ll mod=1e9+7;
vector<ll>arr,cut,tek;
vector<ll>st(4*sz),stc(4*sz),stt(4*sz);
void build(ll v,ll l,ll r,vector<ll>& st,vector<ll>& arr){
    if(l==r){
        st[v]=arr[l];
        //cout<<v<<' '<<st[v]<<endl;
        return;
    }
    ll mid=(l+r)/2;
    build(2*v,l,mid,st,arr);
    build(2*v+1,mid+1,r,st,arr);
    st[v]=st[2*v]^st[2*v+1];
}
void update(ll v,ll l,ll r,ll ind,ll val,vector<ll>& st){
    if(ind<l or ind>r)
    return;
    if(l==r){
        st[v]=val;
        return;
    }
    ll mid=(l+r)/2;
    update(2*v,l,mid,ind,val,st);
    update(2*v+1,mid+1,r,ind,val,st);
    st[v]=st[2*v]^st[2*v+1];
}
ll query(ll v,ll l,ll r,ll sl,ll sr,vector<ll>& st){
    if(sl>r or sr<l)
    return 0;
    if(l>=sl and r<=sr)
    return st[v];
    ll mid=(l+r)/2;
    return (query(2*v,l,mid,sl,sr,st)^query(2*v+1,mid+1,r,sl,sr,st));
}
void work(){
    ll n,q;
    cin>>n>>q;
    arr.resize(n+10);
    tek.pb(0);
    cut.pb(0);
    fori(i,1,n){
        ll x;
        cin>>x;
        arr[i]=x;
        if(i%2==1)
        tek.pb(x);
        else
        cut.pb(x);
    }
    //cout<<"ST:"<<endl;
    build(1,1,n,st,arr);
    //cout<<endl<<"TEK:"<<endl;
    build(1,1,(ll)tek.size(),stt,tek);
    //cout<<endl<<"CUT:"<<endl;
    build(1,1,(ll)cut.size(),stc,cut);
    while(q--){
        ll t;
        cin>>t;
        if(t==1){
            ll val,ind;
            cin>>ind>>val;
            update(1,1,n,ind,val,st);
            if(ind%2==1)
            update(1,1,(ll)tek.size(),ind,val,stt);
            else
            update(1,1,(ll)cut.size(),ind,val,stc);
        }
        else{
            ll l,r;
            cin>>l>>r;
            //ll ans=query(1,1,n,l,r,st);
            ll ans1=0;
            if((r-l+1)%2==0){
                cout<<0<<endl;
            }
            if(l%2==0)
            ans1=query(1,1,(ll)cut.size(),(l+1)/2,(r+1)/2,stc);
            if(l%2==1) 
            ans1=query(1,1,(ll)tek.size(),(l+1)/2,(r+1)/2,stt);
            //cout<<ans<<' '<<ans1<<endl;
            cout<<ans1<<endl;
        }
    }
}
int main(){
    Study;
    ll t=1;
    //cin>>t;
    while(t--){
        work();
    }
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 18
• Subtask 3: 0 / 25
• Subtask 4: 0 / 20
• Subtask 5: 0 / 25