Submission #1219220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219220		lukasuliashvili	XORanges (eJOI19_xoranges)	C++20	100 / 100	392 ms	11332 KiB

xoranges

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define rep(i,a,b) for(int i=a; i<=b; i++)
const int N=2*1e6+5;
int seg[4*N],seg2[4*N],a[N];
void update(int node ,int l,int r, int idx, int u){
	if(l==r){
		seg[node]=u;
        return ;
	}
	int m=(l+r)/2;
	if(m>=idx){
		update(2*node,l,m,idx,u);
	}
	else{
		update(2*node+1,m+1,r,idx,u);
	}
	seg[node]=seg[2*node]^seg[2*node+1];
}
void update2(int node ,int l,int r, int idx, int u){
	if(l==r){
		seg2[node]=u;
        return ;
	}
	int m=(l+r)/2;
	if(m>=idx){
		update2(2*node,l,m,idx,u);
	}
	else{
		update2(2*node+1,m+1,r,idx,u);
	}
	seg2[node]=seg2[2*node]^seg2[2*node+1];
}
int get(int node, int l, int r,int s , int e){
	if(l>e or r<s){
		return 0;
	}
	if(l>=s and r<=e){
		return seg[node];
	}
	int m=(l+r)/2;
	int val1=get(2*node,l,m,s,e);
	int val2=get(2*node+1,m+1,r,s,e);
	return val1^val2;
}
int get1(int node, int l, int r,int s , int e){
	if(l>e or r<s){
		return 0;
	}
	if(l>=s and r<=e){
		return seg2[node];
	}
	int m=(l+r)/2;
	int val1=get1(2*node,l,m,s,e);
	int val2=get1(2*node+1,m+1,r,s,e);
	return val1^val2;
}
signed main(){
	int n, q;cin>>n>>q;	
	rep(i,1,n){
		cin>>a[i];
		update(1,1,n,i,a[i]);
		if(i%2==1)
		update2(1,1,n,i,a[i]);
	}
	rep(i,1,q){
		int type;cin>>type;
		if(type==2){
			int l,r;cin>>l>>r;
			if((r-l+1)%2==0){
				cout<<0<<endl;
			}
			else{
				int val1=get(1,1,n,l,r);
				int val2=get1(1,1,n,l,r);
				if(l%2==1){
					cout<<val2<<endl;
				}
				else{
					cout<<(val1^val2)<<endl;
				}
			}
		}	
		else{
			int l,u;cin>>l>>u;
			update(1,1,n,l,u);
			if(l%2==1)
			update2(1,1,n,l,u);
		}
	}
}

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