oj.uz

Submission #491781

# Submission time Handle Problem Language Result Execution time Memory
491781 2021-12-04T11:16:05 Z uncripted XORanges (eJOI19_xoranges) C++11
100 / 100
 515 ms 9292 KB 
#include<bits/stdc++.h>
using namespace std;
long long fl[400000];
long long fk[400000];
long long a[300000];	
long long n,q;
void updatel(long long s, long long x){
	while(s<=n){
	fl[s]=fl[s]^x;	
	 s+=s&(-s);	
	}
}	
long long getl(long long s){
	long long sum=0;
	while(s>0){
	
		sum=sum^fl[s];
		s-=s&(-s);	
	}
	return sum;
}

void updatek(long long s, long long x){
	while(s<=n){
	fk[s]=fk[s]^x;	
 	s+=s&(-s);	
	}
}	
long long getk(long long s){
	long long sum=0;
	while(s>0){
	
		sum=sum^fk[s];
		s-=s&(-s);	
	}
	return sum;
}

int main(){

	cin>>n>>q;

	for(long long i=1; i<=n; i++){
		cin>>a[i];
		if(i%2==0){
			updatel(i/2, a[i]);
		}else{
			updatek(i/2+1, a[i]);
		}
	}
	for(long long i=0; i<q; i++){
		long long qur;
		cin>>qur;
		if(qur==1){
			long long x,y;
			cin>>x>>y;
			if(x%2==0){
				updatel(x/2, y^a[x]);
			}else{
				updatek(x/2+1, y^a[x]);
			}
			a[x]=y;
		}else{
			long long x,y;
			cin>>x>>y;
			if((y-x+1)%2==0){
				cout<<"0"<<endl;
				continue;
			}
			if(x%2==0){
				long long tot;
			
				tot=getl(y/2)^(getl(x/2-1));
				cout<<tot<<endl;
			}else{
				long long tot;
				
				tot=getk(y/2+1)^(getk(x/2));
				cout<<tot<<endl;
			}	
		}
	}
	
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 304 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 308 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 13 ms 460 KB Output is correct
12 Correct 11 ms 532 KB Output is correct
13 Correct 16 ms 532 KB Output is correct
14 Correct 13 ms 600 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 7492 KB Output is correct
2 Correct 515 ms 7532 KB Output is correct
3 Correct 488 ms 7480 KB Output is correct
4 Correct 491 ms 7464 KB Output is correct
5 Correct 472 ms 7596 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 2 ms 304 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 2 ms 308 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 13 ms 460 KB Output is correct
12 Correct 11 ms 532 KB Output is correct
13 Correct 16 ms 532 KB Output is correct
14 Correct 13 ms 600 KB Output is correct
15 Correct 471 ms 7492 KB Output is correct
16 Correct 515 ms 7532 KB Output is correct
17 Correct 488 ms 7480 KB Output is correct
18 Correct 491 ms 7464 KB Output is correct
19 Correct 472 ms 7596 KB Output is correct
20 Correct 378 ms 9192 KB Output is correct
21 Correct 392 ms 9164 KB Output is correct
22 Correct 393 ms 9292 KB Output is correct
23 Correct 431 ms 9076 KB Output is correct
24 Correct 467 ms 9208 KB Output is correct