Submission #760293

#	Time	Username	Problem	Language	Result	Execution time	Memory
760293		DJeniUp	XORanges (eJOI19_xoranges)	C++17	0 / 100	482 ms	10856 KiB

xoranges

#include "bits/stdc++.h"
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,ull>pairull;
typedef pair<ll,pairll>pair3l;
typedef long double ld;
typedef pair<ld,ll>pairld;
 
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define N 100007
//#define MOD 998244353
#define INF 1000000000000000007
#define eps 0.0000000001
 
ll n,m,d[2*N],t[2][8*N];

void BT(ll x,ll l,ll r){
    if(l==r){
        t[0][x]=d[l];
        return ;
    }
    ll m1=(l+r)/2;
    BT(x*2+1,l,m1);
    BT(x*2+2,m1+1,r);
    t[0][x]=(t[0][x*2+1]^t[0^((m1-l+1)%2)][x*2+2]);
    t[1][x]=(t[1][x*2+1]^t[1^((m1-l+1)%2)][x*2+2]);
    return ;
}

void A(ll x,ll l,ll r,ll tl,ll y){
    if(r<tl || tl<l)return ;
    if(l==r){
        t[0][x]=y;
        return ;
    }
    ll m1=(l+r)/2;
    A(x*2+1,l,m1,tl,y);
    A(x*2+2,m1+1,r,tl,y);
    t[0][x]=(t[0][x*2+1]^t[0^((m1-l+1)%2)][x*2+2]);
    t[1][x]=(t[1][x*2+1]^t[1^((m1-l+1)%2)][x*2+2]);
    return ;
}

ll R(ll x,ll l,ll r,ll tl,ll tr,ll y){
    if(r<tl || tr<l)return 0;
    if(tl<=l && r<=tr)return t[y][x];
    ll m1=(l+r)/2;
    return (R(x*2+1,l,m1,tl,tr,y)^R(x*2+2,m1+1,r,tl,tr,(y^(m1-l+1)%2)));
}

int main(){
    
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>d[i];
    }
    BT(0,1,n);
    for(int i=1;i<=m;i++){
        ll tp;
        cin>>tp;
        if(tp==1){
            ll x,y;
            cin>>x>>y;
            A(0,1,n,x,y);
        }else{
            ll x,y;
            cin>>x>>y;
            if((y-x)%2==1)cout<<0<<endl;
            else cout<<R(0,1,n,x,y,0)<<endl;
        }
    }
 
    return 0;
}

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