Submission #999760

#	Time	Username	Problem	Language	Result	Execution time	Memory
999760		ayankarimova	XORanges (eJOI19_xoranges)	C++14	100 / 100	91 ms	18972 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
const ll sz=2e5+5;
ll s1[sz*4], s2[sz*4], a[sz], b[sz];
void build1(ll l, ll r, ll in)
{
    if(l==r){
        s1[in]=a[l];
        return;
    }
    ll mid=(l+r)/2;
    build1(l, mid, in*2);
    build1(mid+1, r, in*2+1);
    s1[in]=(s1[in*2]^s1[in*2+1]);
}
void build2(ll l, ll r, ll in)
{
    if(l==r){
        s2[in]=b[l];
        return;
    }
    ll mid=(l+r)/2;
    build2(l, mid, in*2);
    build2(mid+1, r, in*2+1);
    s2[in]=(s2[in*2]^s2[in*2+1]);
}
void update1(ll l, ll r, ll in, ll ind, ll val)
{
    if(ind<l || ind>r) return;
    if(l==r){
        s1[in]=val;
        return;
    }
    ll mid=(l+r)/2;
    update1(l, mid, in*2, ind, val);
    update1(mid+1, r, in*2+1, ind, val);
    s1[in]=(s1[in*2]^s1[in*2+1]);
}
void update2(ll l, ll r, ll in, ll ind, ll val)
{
    if(ind<l || ind>r) return;
    if(l==r){
        s2[in]=val;
        return;
    }
    ll mid=(l+r)/2;
    update2(l, mid, in*2, ind, val);
    update2(mid+1, r, in*2+1, ind, val);
    s2[in]=(s2[in*2]^s2[in*2+1]);
}
ll ans1(ll l, ll r, ll in, ll ql, ll qr)
{
    if(ql>r || qr<l) return 0;
    if(ql<=l && r<=qr){
        return s1[in];
    }
    ll mid=(l+r)/2;
    return (ans1(l, mid, in*2, ql, qr)^ans1(mid+1, r, in*2+1, ql, qr));
}
ll ans2(ll l, ll r, ll in, ll ql, ll qr)
{
    if(ql>r || qr<l) return 0;
    if(ql<=l && r<=qr){
        return s2[in];
    }
    ll mid=(l+r)/2;
    return (ans2(l, mid, in*2, ql, qr)^ans2(mid+1, r, in*2+1, ql, qr));
}
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    ll n, q;
    cin>>n>>q;
    for(int i=1; i<=n; i++){
        if(i%2){
            cin>>a[i];
        }
        else{
            cin>>b[i];
        }
    }
    build1(1, n, 1);
    build2(1, n, 1);
    while(q--){
        ll t, l, r;
        cin>>t>>l>>r;
        if(t==1){
            if(l%2){
                update1(1, n, 1, l, r);
            }
            else{
                update2(1, n, 1, l, r);
            }
        }
        else{
            if((l-r+1)%2==0){
                cout<<0<<endl;
            }
            else{
                if(l%2){
                    cout<<ans1(1, n, 1, l, r)<<endl;
                }
                else{
                    cout<<ans2(1, n, 1, l, r)<<endl;
                }
            }
        }
    }
}

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