oj.uz

Submission #787759

# Submission time Handle Problem Language Result Execution time Memory
787759 2023-07-19T12:15:27 Z ThylOne XORanges (eJOI19_xoranges) C++14
100 / 100
 407 ms 11988 KB 
#include<bits/stdc++.h>

using namespace std;

#define int long long
const int DEPTH = 18;
const int LEAF = (1<<(DEPTH-1));
const int NB_NODES = (1<<DEPTH);
const int MAXI = 2 * 100000+2;
struct XorTree{
	int vals[NB_NODES];
	void init(){
		for(int i = 0;i<NB_NODES;i++){
			vals[i]=0;
		}
	};
	void update(int pos,int val){
		int node = pos+LEAF;
		int varia = val^vals[node];
		while(node!=1){
			vals[node]^=varia;
			node/=2;
		}
		vals[1]^=varia;
	}
	int _getVal(int gauche,int droite){
		if(droite<gauche){
			return 0;
		}
		if(gauche&1){
			return vals[gauche]^_getVal(gauche+1,droite);
		}
		if(!(droite&1)){
			return vals[droite]^_getVal(gauche,droite-1);
		}
		return _getVal(gauche/2,droite/2);
	}
	int getVal(int gauche,int droite){
		return _getVal(gauche+LEAF,droite+LEAF);
	}
	

};

#include<bits/stdc++.h>
 
using namespace std;
#define int long long
signed main(){
	
	XorTree XT[2];
	XT[0].init();
	XT[1].init();
	int n;cin>>n;
	int q;cin>>q;
	vector<int> nums(n);
	for(int i = 0 ; i < n ; i++){
		cin>>nums[i];
		XT[i%2].update(i/2,nums[i]);
	}
	
	
	
	
	
	for(int _=0;_<q;_++){
		int type;cin>>type;
		if(type==1){
			int pos;cin>>pos;pos--;
			int val;cin>>val;
			XT[pos%2].update(pos/2,val);
		}else{
			int l,r;cin>>l>>r;
			l--;r--;
			if(((r-l)&1)){
				cout<<0<<endl;
			}else{
				if((l/2-1)<0){
					int ans = XT[r%2].getVal(0,r/2);
					cout<<ans<<endl;
				}else{
					int ans = XT[r%2].getVal(0,r/2)^XT[r%2].getVal(0,l/2-1);
					cout<<ans<<endl;
				}
			
				
			}
			
		}
	}
	return 0;
}

/*
 int n;cin>>n;
	int q;cin>>q;
	vector<int> nums(n);
	for(int i = 0 ; i < n ; i++){
		cin>>nums[i];
	}
	int XorPref[n];
	
	int acts[2] = {0,0};
	for(int i = 0;i<n;i++){
		acts[i%2]^=nums[i];
		XorPref[i]=acts[i%2];
	}
	
	for(int _=0;_<q;_++){
		int type;cin>>type;
		if(type==1){
			int pos;cin>>pos;pos--;
			int val;cin>>val;
			nums[pos]=val;
		}else{
			int l,r;cin>>l>>r;
			l--;r--;
			if(((r-l)&1)){
				cout<<0<<endl;
			}else{
				if((l-2)<0){
					int ans = XorPref[r];
					cout<<ans<<endl;
				}else{
					int ans = XorPref[r]^XorPref[l-2];
					cout<<ans<<endl;
				}
			
				
			}
			
		}
	}
	return 0;
 */

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4420 KB Output is correct
2 Correct 3 ms 4404 KB Output is correct
3 Correct 3 ms 4352 KB Output is correct
4 Correct 3 ms 4308 KB Output is correct
5 Correct 3 ms 4408 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 2 ms 4308 KB Output is correct
5 Correct 2 ms 4308 KB Output is correct
6 Correct 3 ms 4420 KB Output is correct
7 Correct 3 ms 4404 KB Output is correct
8 Correct 3 ms 4352 KB Output is correct
9 Correct 3 ms 4308 KB Output is correct
10 Correct 3 ms 4408 KB Output is correct
11 Correct 9 ms 4540 KB Output is correct
12 Correct 9 ms 4548 KB Output is correct
13 Correct 11 ms 4564 KB Output is correct
14 Correct 11 ms 4564 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 401 ms 11912 KB Output is correct
2 Correct 407 ms 11972 KB Output is correct
3 Correct 399 ms 11988 KB Output is correct
4 Correct 379 ms 11596 KB Output is correct
5 Correct 388 ms 11728 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4308 KB Output is correct
2 Correct 2 ms 4308 KB Output is correct
3 Correct 2 ms 4308 KB Output is correct
4 Correct 2 ms 4308 KB Output is correct
5 Correct 2 ms 4308 KB Output is correct
6 Correct 3 ms 4420 KB Output is correct
7 Correct 3 ms 4404 KB Output is correct
8 Correct 3 ms 4352 KB Output is correct
9 Correct 3 ms 4308 KB Output is correct
10 Correct 3 ms 4408 KB Output is correct
11 Correct 9 ms 4540 KB Output is correct
12 Correct 9 ms 4548 KB Output is correct
13 Correct 11 ms 4564 KB Output is correct
14 Correct 11 ms 4564 KB Output is correct
15 Correct 401 ms 11912 KB Output is correct
16 Correct 407 ms 11972 KB Output is correct
17 Correct 399 ms 11988 KB Output is correct
18 Correct 379 ms 11596 KB Output is correct
19 Correct 388 ms 11728 KB Output is correct
20 Correct 304 ms 11688 KB Output is correct
21 Correct 299 ms 11712 KB Output is correct
22 Correct 361 ms 11712 KB Output is correct
23 Correct 383 ms 11656 KB Output is correct
24 Correct 377 ms 11616 KB Output is correct