Submission #681517

#	Time	Username	Problem	Language	Result	Execution time	Memory
681517		peijar	XORanges (eJOI19_xoranges)	C++17	100 / 100	520 ms	9552 KiB

xoranges

#include <bits/stdc++.h>
//#define int long long
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define all(v) v.begin(), v.end()
using namespace std;
 
const int N = (1 << 18);
int tXor[2][N * 2];
 
int getXor(int ind, int gauche, int droite){
	if (droite < gauche) return 0;
	if (gauche%2 == 1) return tXor[ind][gauche]^getXor(ind, gauche + 1, droite);
	if (droite%2 == 0) return tXor[ind][droite]^getXor(ind, gauche, droite - 1);
	return getXor(ind, gauche/2, droite/2);
}
 
void actualiser(int ind, int noeud, int val){
	tXor[ind][noeud] = val; noeud /= 2;
	for (; noeud > 0; noeud /= 2) tXor[ind][noeud] = tXor[ind][noeud * 2]^tXor[ind][noeud * 2 + 1];
}
 
signed main(){
	int nVals, nReqs; cin >> nVals >> nReqs;
	for (int iVal = 0; iVal < nVals; ++iVal){
		int val; cin >> val;
		actualiser(iVal%2, N + iVal, val);
	}
	
	while (nReqs--){
		int typeReq; cin >> typeReq;
		if (typeReq == 1){
			int noeud, val; cin >> noeud >> val;
			actualiser(1 - noeud%2, N + noeud - 1, val);
		}
		else {
			int gauche, droite; cin >> gauche >> droite;
			if ((droite - gauche)%2 == 1) cout << 0 << endl;
			else cout << getXor(1 - gauche%2, N + gauche - 1, N + droite - 1) << endl;
		}
	}
	return 0;
}

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