Submission #466149

#	Time	Username	Problem	Language	Result	Execution time	Memory
466149		okaragul	XORanges (eJOI19_xoranges)	C++17	100 / 100	707 ms	15124 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define endl "\n"
#define all(aa) aa.begin(), aa.end()

vector<int> arr;
vector<vector<int>> st;

int build(int n, int s, int e, int t){
	if(s==e) return st[t][n]=(s%2==t ? arr[s]:0);
	int mid=(s+e)/2;
	return st[t][n]=build(n*2, s, mid, t)^build(n*2+1, mid+1, e, t);
}

int query(int n, int s, int e, int l, int r, int t){
	if(s>=l && e<=r) return st[t][n];
	if(s>r || e<l) return 0;
	int mid=(s+e)/2;
	return query(n*2, s, mid, l, r, t)^query(n*2+1, mid+1, e, l, r, t);
}

int update(int n, int s, int e, int i, int v, int t){
	if(s>i || e<i) return st[t][n];
	if(s==e) return st[t][n]=v;
	int mid=(s+e)/2;
	return st[t][n]=update(n*2, s, mid, i, v, t)^update(n*2+1, mid+1, e, i, v, t);
}

int main(){
	int n, q;
	cin>>n>>q;

	arr.resize(n+1); st.resize(2, vector<int>(6*n));
	for(int i=1; i<=n; i++) cin>>arr[i];

	build(1, 1, n, 0); build(1, 1, n, 1);
	while(q--){
		int t, a, b;
		cin>>t>>a>>b;

		if(t==1) update(1, 1, n, a, b, a%2);
		else if((b-a)%2) cout<<0<<endl;
		else cout<<query(1, 1, n, a, b, a%2)<<endl;
	}
}

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