Submission #290376

#	Time	Username	Problem	Language	Result	Execution time	Memory
290376		dolijan	XORanges (eJOI19_xoranges)	C++14	100 / 100	632 ms	10504 KiB

xoranges

#include <bits/stdc++.h>
typedef long long ll;
#define pb push_back;
using namespace std;
const int sz=530069;
int parni[sz];
int neparni[sz];
void updateparni(int pos,int val)
{
	parni[pos]=val;
	pos/=2;
	while(pos>=1)
	{
		parni[pos]=parni[2*pos]^parni[2*pos+1];
		pos/=2;
	}
}
void updateneparni(int pos,int val)
{
	neparni[pos]=val;
	pos/=2;
	while(pos>=1)
	{
		neparni[pos]=neparni[2*pos]^neparni[2*pos+1];
		pos/=2;
	}
}
int queryparni(int l,int r,int L,int R,int node)
{
	if(R<l || r<L) return 0;
	if(l<=L && R<=r) return parni[node];
	int mid=(L+R)/2;
	int levo=queryparni(l,r,L,mid,2*node);
	int desno=queryparni(l,r,mid+1,R,2*node+1);
	return levo^desno;
}
int queryneparni(int l,int r,int L,int R,int node)
{
	if(R<l || r<L) return 0;
	if(l<=L && R<=r) return neparni[node];
	int mid=(L+R)/2;
	int levo=queryneparni(l,r,L,mid,2*node);
	int desno=queryneparni(l,r,mid+1,R,2*node+1);
	return levo^desno;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,q;
	cin>>n>>q;
	int a[n+1];
	for(int i=1;i<=n;i++) cin>>a[i];
	int k=1;
	while(k<n) k*=2;
	for(int i=1;i<=n;i++)
	{
		if(i%2==1) updateneparni(i-1+k,a[i]);
		else updateparni(i-1+k,a[i]);
	}
	while(q--)
	{
		int type,aa,bb;
		cin>>type>>aa>>bb;
		if(type==1) 
		{
			a[aa]=bb;
			if(aa%2==1) updateneparni(aa-1+k,bb);
			else updateparni(aa-1+k,bb);
		}
		else
		{
			if(aa%2!=bb%2) cout<<0<<endl;
			else
			{
				if(aa%2==0) cout<<queryparni(aa-1,bb-1,0,k-1,1)<<endl;
				else cout<<queryneparni(aa-1,bb-1,0,k-1,1)<<endl;
			}
		}
	}	
	return 0;
}

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