oj.uz

Submission #307576

# Submission time Handle Problem Language Result Execution time Memory
307576 2020-09-28T16:31:03 Z Mounir XORanges (eJOI19_xoranges) C++14
100 / 100
 988 ms 9848 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 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 18 ms 512 KB Output is correct
12 Correct 18 ms 512 KB Output is correct
13 Correct 23 ms 512 KB Output is correct
14 Correct 22 ms 512 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 964 ms 8288 KB Output is correct
2 Correct 988 ms 9848 KB Output is correct
3 Correct 961 ms 9592 KB Output is correct
4 Correct 924 ms 9244 KB Output is correct
5 Correct 932 ms 9212 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 18 ms 512 KB Output is correct
12 Correct 18 ms 512 KB Output is correct
13 Correct 23 ms 512 KB Output is correct
14 Correct 22 ms 512 KB Output is correct
15 Correct 964 ms 8288 KB Output is correct
16 Correct 988 ms 9848 KB Output is correct
17 Correct 961 ms 9592 KB Output is correct
18 Correct 924 ms 9244 KB Output is correct
19 Correct 932 ms 9212 KB Output is correct
20 Correct 755 ms 9252 KB Output is correct
21 Correct 766 ms 9336 KB Output is correct
22 Correct 764 ms 9392 KB Output is correct
23 Correct 908 ms 9720 KB Output is correct
24 Correct 914 ms 9336 KB Output is correct