Submission #274726

#	Time	Username	Problem	Language	Result	Execution time	Memory
274726		keta_tsimakuridze	XORanges (eJOI19_xoranges)	C++14	100 / 100	240 ms	11256 KiB

xoranges

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,q,k,a[N],ind,x,l,r,tree[2][4*N];
void update(int u,int ind,int l,int r,int val,int p) {
	
	if(l>ind || r<ind) return;
	if(ind<=l && r<=ind) {
		tree[p][u]^=val;
		return;
	}
	int mid=(l+r)/2;
	update(2*u,ind,l,mid,val,p);
	update(2*u+1,ind,mid+1,r,val,p);
	tree[p][u]=tree[p][2*u]^tree[p][2*u+1];
}
int getans(int u,int start,int end,int l,int r,int p) {
	
	if(l>end || r<start) return 0;
	if(start<=l && r<=end) {
		return tree[p][u];
	}
	int mid=(l+r)/2;
	return getans(2*u,start,end,l,mid,p)^
	       getans(2*u+1,start,end,mid+1,r,p);
	//tree[u]=tree[2*u]^tree[2*u+1];
}

int main() {
	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(k=1; k<=n; k++) {
		cin>>a[k];
		if(k%2==1) update(1,k,1,n,a[k],1);
		else update(1,k,1,n,a[k],0);
	
	}
	for(k=1; k<=q; k++) {
		cin>>x;
		if(x==1) {
			cin>>ind>>x; 
			if(ind%2==0) update(1,ind,1,n,a[ind]^x,0);
			else update(1,ind,1,n,a[ind]^x,1);
			a[ind]=x;	//cout<<getans(1,1,n,1,n,1)<<"+"<<endl;
		} else {
			cin>>l>>r;
			if((r-l+1)%2==0) cout<<0<<" ";
			else {

				cout<<getans(1,l,r,1,n,r%2)<<" ";
			}
		}
	}
}

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