Submission #1089116

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1089116	2024-09-16T05:17:10 Z	Muhammet	XORanges (eJOI19_xoranges)	C++17	100 / 100	397 ms	9300 KB

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.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	444 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct

Subtask #2

18.0 / 18.0

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

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	444 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	7 ms	604 KB	Output is correct
12	Correct	7 ms	572 KB	Output is correct
13	Correct	9 ms	664 KB	Output is correct
14	Correct	11 ms	664 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	395 ms	9296 KB	Output is correct
2	Correct	386 ms	9156 KB	Output is correct
3	Correct	393 ms	9300 KB	Output is correct
4	Correct	375 ms	8788 KB	Output is correct
5	Correct	395 ms	8752 KB	Output is correct

Subtask #5

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	444 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	7 ms	604 KB	Output is correct
12	Correct	7 ms	572 KB	Output is correct
13	Correct	9 ms	664 KB	Output is correct
14	Correct	11 ms	664 KB	Output is correct
15	Correct	395 ms	9296 KB	Output is correct
16	Correct	386 ms	9156 KB	Output is correct
17	Correct	393 ms	9300 KB	Output is correct
18	Correct	375 ms	8788 KB	Output is correct
19	Correct	395 ms	8752 KB	Output is correct
20	Correct	295 ms	8828 KB	Output is correct
21	Correct	303 ms	9044 KB	Output is correct
22	Correct	321 ms	9040 KB	Output is correct
23	Correct	393 ms	8904 KB	Output is correct
24	Correct	397 ms	8788 KB	Output is correct