oj.uz

Submission #681517

# Submission time Handle Problem Language Result Execution time Memory
681517 2023-01-13T08:54:56 Z peijar XORanges (eJOI19_xoranges) C++17
100 / 100
 520 ms 9552 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 316 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 2 ms 320 KB Output is correct
5 Correct 2 ms 340 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 320 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 13 ms 580 KB Output is correct
12 Correct 10 ms 576 KB Output is correct
13 Correct 11 ms 580 KB Output is correct
14 Correct 11 ms 468 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 9492 KB Output is correct
2 Correct 510 ms 9520 KB Output is correct
3 Correct 483 ms 9552 KB Output is correct
4 Correct 479 ms 9132 KB Output is correct
5 Correct 505 ms 9136 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 316 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 2 ms 320 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 13 ms 580 KB Output is correct
12 Correct 10 ms 576 KB Output is correct
13 Correct 11 ms 580 KB Output is correct
14 Correct 11 ms 468 KB Output is correct
15 Correct 520 ms 9492 KB Output is correct
16 Correct 510 ms 9520 KB Output is correct
17 Correct 483 ms 9552 KB Output is correct
18 Correct 479 ms 9132 KB Output is correct
19 Correct 505 ms 9136 KB Output is correct
20 Correct 392 ms 9292 KB Output is correct
21 Correct 379 ms 9216 KB Output is correct
22 Correct 383 ms 9256 KB Output is correct
23 Correct 483 ms 9172 KB Output is correct
24 Correct 465 ms 9228 KB Output is correct