Submission #407143

#	Time	Username	Problem	Language	Result	Execution time	Memory
407143		luka1234	XORanges (eJOI19_xoranges)	C++14	100 / 100	646 ms	9244 KiB

xoranges

#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
using namespace std;  
int a1[100001],a2[100001];
int t1[400001];
int t2[400001];
void build1(int v,int tl,int tr){
	if(tl==tr)
	   t1[v]=a1[tl];
	else{
		int m=(tl+tr)/2;
		build1(2*v,tl,m);
		build1(2*v+1,m+1,tr);
		t1[v]=t1[2*v]^t1[2*v+1];
	}
}
int get1(int v,int tl,int tr,int l,int r){
	if(l==tl&&r==tr)
	   return t1[v];
	int m=(tl+tr)/2;
	if(r<=m)
	   return get1(2*v,tl,m,l,r);
	else{
		if(l>m)
		   return get1(2*v+1,m+1,tr,l,r);
		else{
			return get1(2*v,tl,m,l,m)^get1(2*v+1,m+1,tr,m+1,r);
		}
	}
}
void update1(int v,int tl,int tr,int p,int x){
	if(tl==tr)
	   t1[v]=x;
	else{
		int m=(tl+tr)/2;
		if(p<=m)
		   update1(2*v,tl,m,p,x);
		else
		   update1(2*v+1,m+1,tr,p,x);
		t1[v]=t1[2*v]^t1[2*v+1];
	}
}
void build2(int v,int tl,int tr){
	if(tl==tr)
	   t2[v]=a2[tl];
	else{
		int m=(tl+tr)/2;
		build2(2*v,tl,m);
		build2(2*v+1,m+1,tr);
		t2[v]=t2[2*v]^t2[2*v+1];
	}
}
int get2(int v,int tl,int tr,int l,int r){
	if(l==tl&&r==tr)
	   return t2[v];
	int m=(tl+tr)/2;
	if(r<=m)
	   return get2(2*v,tl,m,l,r);
	else{
		if(l>m)
		   return get2(2*v+1,m+1,tr,l,r);
		else{
			return get2(2*v,tl,m,l,m)^get2(2*v+1,m+1,tr,m+1,r);
		}
	}
}
void update2(int v,int tl,int tr,int p,int x){
	if(tl==tr)
	   t2[v]=x;
	else{
		int m=(tl+tr)/2;
		if(p<=m)
		   update2(2*v,tl,m,p,x);
		else
		   update2(2*v+1,m+1,tr,p,x);
		t2[v]=t2[2*v]^t2[2*v+1];
	}
}
int main(){
    int n,t,cnt1=1,cnt2=1;
    cin>>n>>t;
    for(int k=1;k<=n;k++){
    	if(k%2==0)
    	   cin>>a1[cnt1],cnt1++;
    	else
    	   cin>>a2[cnt2],cnt2++;
	}
	build1(1,1,cnt1-1);
	build2(1,1,cnt2-1);
	while(t--){
		int aa,b,c;
		cin>>aa>>b>>c;
		if(aa==2){
			int len=c-b+1;
			if(len%2==0)
			   cout<<0<<"\n";
			else{
				int ans;
				 if(b%2==0){
				 	ans=get1(1,1,cnt1-1,b/2,c/2);
				 }
				 else{
				 	ans=get2(1,1,cnt2-1,b/2+1,c/2+1);
				 }
				cout<<ans<<"\n";
			}
		}
		else{
			if(b%2==0){
				update1(1,1,cnt1-1,b/2,c);
			}
			else{
				update2(1,1,cnt2-1,b/2+1,c);
			}
		}
	}
    return 0;
}

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