Submission #1089116

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089116		Muhammet	XORanges (eJOI19_xoranges)	C++17	100 / 100	397 ms	9300 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+5;

int n, q, st[5][N*4];

vector <int> a;

int bld(int nd, int l, int r, bool z){
	if(l == r) return st[z][nd] = a[l*2-z];
	int md = (l + r)  / 2;
	return st[z][nd] = (bld(nd*2,l,md,z) ^ bld(nd*2+1,md+1,r,z));
}

int upd(int nd, int l, int r, int ind, int vl, bool z){
	if(l > ind or r < ind) return st[z][nd];
	if(l == r) return st[z][nd] = vl;
	int md = (l + r) / 2;
	return st[z][nd] = (upd(nd*2,l,md,ind,vl,z) ^ upd(nd*2+1,md+1,r,ind,vl,z));
}

int fnd(int nd, int l, int r, int x, int y, bool z){
	if(l > y or r < x) return 0;
	if(l >= x and r <= y) return st[z][nd];
	int md = (l + r) / 2;
	return (fnd(nd*2,l,md,x,y,z) ^ fnd(nd*2+1,md+1,r,x,y,z));
}

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

	a.assign(n+1,0);

	for(int i = 1; i <= n; i++){
		cin >> a[i];
	}

	if(n > 1) bld(1,1,n/2,0);
	bld(1,1,(n+1)/2,1);

	while(q--){
		int t, l, r;
		cin >> t >> l >> r;
		int x = (l%2);
		if(t == 1){
			upd(1,1,(n+x)/2,(l+x)/2,r,x);
		}
		else {
			if((r-l+1) % 2 == 0){
				cout << 0 << '\n';
			}
			else {
				cout << fnd(1,1,(n+x)/2,(l+x)/2,(r+x)/2,x) << '\n';
			}
		}
	}
}

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