Submission #268077

#	Time	Username	Problem	Language	Result	Execution time	Memory
268077		VusetOrucov	XORanges (eJOI19_xoranges)	C++17	100 / 100	641 ms	16248 KiB

xoranges

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define black_tree tree<ll,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update>
#define gp __gnu_pbds
#define INF 1000000000
#define MOD 1000000007
#define MAX 200001
#define endl '\n'
#define ll long long
#define ld long double
#define lli long long int
#define ull unsigned long long
#define ulli unsigned long long int
#define pb push_back
#define pf push_front
#define ook order_of_key
#define fbo find_by_order
#define np next_permutation
#define mp make_pair
#define eb emplace_back 
#define me max_element
#define lb lower_bound 
#define ub upper_bound
#define bs binary_search
#define ff first
#define ss second
using namespace std;
using namespace gp;
ll n,q,k,u,v,a[MAX],dp0[4*MAX],dp1[4*MAX];
void buildTree(ll v,ll l,ll r){
    if(l==r){
    	if(l%2==1){
    		dp0[v]=a[l];
		}
		else{
			dp1[v]=a[l];
		}
        return;
    }
    ll m=(l+r)/2;
    buildTree(2*v,l,m);
    buildTree(2*v+1,m+1,r);
    dp0[v]=dp0[2*v]^dp0[2*v+1];
    dp1[v]=dp1[2*v]^dp1[2*v+1];
}
ll get(ll v,ll l,ll r,ll i1,ll i2,ll t){
    if(r<i1 || l>i2){
    	return 0;
	}
    else if(l>=i1 && r<=i2){
    	if(t==1){
    		return dp0[v];
		}
		else{
			return dp1[v];
		}
	}
    ll m=(l+r)/2;
    ll ans=get(2*v,l,m,i1,min(m,i2),t);
    ll sum=get(2*v+1,m+1,r,max(m+1,i1),i2,t);
    return ans^sum;
}
void updateTree(ll v,ll l,ll r,ll i,ll value){
    if(l==r){
    	if(i%2==1){
    		dp0[v]=value;
		}
        else{
        	dp1[v]=value;
		}
        return;
    }
    ll m=(l+r)/2;
    if(i<=m){
    	updateTree(2*v,l,m,i,value);
	}
    else{
    	updateTree(2*v+1,m+1,r,i,value);
	}
    dp0[v]=dp0[2*v]^dp0[2*v+1];
    dp1[v]=dp1[2*v]^dp1[2*v+1];
}
int main(){
	ios::sync_with_stdio(true);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	buildTree(1,1,n);
	while(q--){
		cin>>k>>u>>v;
		if(k==1){
			updateTree(1,1,n,u,v);
		}
		else{
			if(u%2!=v%2){
				cout<<"0\n";
			}
			else{
				cout<<get(1,1,n,u,v,u%2)<<endl;
			}
		}
	}
}

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