Submission #896803

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
896803	2024-01-02T07:47:28 Z	Jawad_Akbar_JJ	XORanges (eJOI19_xoranges)	C++17	100 / 100	454 ms	12800 KB

xoranges

#include <iostream>
#include <vector>


using namespace std;
const int N = (1<<18) + 1;

struct node{
	int xr = 0;
} sg[N<<2][2];

void insert(int i,int v,int cur = 1,int st = 1,int en = N){
	if (i>=en or i<st)
		return;
	// cout<<st<<" "<<en<<endl;
	sg[cur][i%2].xr ^= v;
	if (en - st == 1)
		return;

	int lc = cur + cur,rc = lc + 1,mid = (st + en)/2;

	insert(i,v,lc,st,mid);
	insert(i,v,rc,mid,en);
}

int get(int l,int r,int t,int cur = 1,int st = 1,int en = N){
	if (l>=en or r<=st)
		return 0;

	if (l<=st and r>=en)
		return sg[cur][t].xr;

	int lc = cur + cur,rc = lc + 1,mid = (st + en)/2;

	return get(l,r,t,lc,st,mid) ^ get(l,r,t,rc,mid,en);
}
int arr[N];
int main(){
	// insert(1,2);
	int n,m;
	cin>>n>>m;

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

	while (m--){
		int t;
		cin>>t;

		if (t==1){
			int i,a;
			cin>>i>>a;
			insert(i,arr[i]);
			insert(i,a);
			arr[i] = a;
		}
		else{
			int l,r;
			cin>>l>>r;

			if ((r - l + 1)%2==0)
				cout<<0<<'\n';
			else
				cout<<get(l,r+1,l%2)<<'\n';
		}
	}
}

Subtask #1

12.0 / 12.0

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

Subtask #2

18.0 / 18.0

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

Subtask #3

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4536 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	2 ms	4444 KB	Output is correct
7	Correct	2 ms	4444 KB	Output is correct
8	Correct	2 ms	4444 KB	Output is correct
9	Correct	2 ms	4444 KB	Output is correct
10	Correct	2 ms	4444 KB	Output is correct
11	Correct	9 ms	4692 KB	Output is correct
12	Correct	9 ms	4444 KB	Output is correct
13	Correct	11 ms	4444 KB	Output is correct
14	Correct	12 ms	4444 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	454 ms	12644 KB	Output is correct
2	Correct	452 ms	12800 KB	Output is correct
3	Correct	439 ms	12620 KB	Output is correct
4	Correct	430 ms	12376 KB	Output is correct
5	Correct	429 ms	12368 KB	Output is correct

Subtask #5

25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	4440 KB	Output is correct
2	Correct	1 ms	4444 KB	Output is correct
3	Correct	1 ms	4536 KB	Output is correct
4	Correct	1 ms	4444 KB	Output is correct
5	Correct	1 ms	4444 KB	Output is correct
6	Correct	2 ms	4444 KB	Output is correct
7	Correct	2 ms	4444 KB	Output is correct
8	Correct	2 ms	4444 KB	Output is correct
9	Correct	2 ms	4444 KB	Output is correct
10	Correct	2 ms	4444 KB	Output is correct
11	Correct	9 ms	4692 KB	Output is correct
12	Correct	9 ms	4444 KB	Output is correct
13	Correct	11 ms	4444 KB	Output is correct
14	Correct	12 ms	4444 KB	Output is correct
15	Correct	454 ms	12644 KB	Output is correct
16	Correct	452 ms	12800 KB	Output is correct
17	Correct	439 ms	12620 KB	Output is correct
18	Correct	430 ms	12376 KB	Output is correct
19	Correct	429 ms	12368 KB	Output is correct
20	Correct	346 ms	12500 KB	Output is correct
21	Correct	336 ms	12368 KB	Output is correct
22	Correct	348 ms	12796 KB	Output is correct
23	Correct	438 ms	12368 KB	Output is correct
24	Correct	417 ms	12340 KB	Output is correct