oj.uz

Submission #300084

# Submission time Handle Problem Language Result Execution time Memory
300084 2020-09-16T13:55:57 Z Khizri XORanges (eJOI19_xoranges) C++17
12 / 100
 1000 ms 8184 KB 
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
const int mxn=2e5+5;
ll arr[mxn],tree[4*mxn];
void build_tree(int id,int l,int r){
	if(l==r){
		tree[id]=arr[l];
		return;
	}
	int m=(l+r)/2;
	build_tree(2*id,l,m);
	build_tree(2*id+1,m+1,r);
	tree[id]=tree[2*id]^tree[2*id+1];
}
ll find_xor(int id,int l,int r,int i1,int i2){
	if(i1>i2){
		return 0;
	}
	if(l==i1&&r==i2){
		return tree[id];
	}
	int m=(l+r)/2;
	ll a=find_xor(2*id,l,m,i1,min(m,i2));
	ll b=find_xor(2*id+1,m+1,r,max(i1,m+1),i2);
	return a^b;
}
void update_tree(int id,int l,int r,int ind,int value){
	if(l==r){
		tree[id]=value;
		return;
	}
	int m=(l+r)/2;
	if(ind<=m) update_tree(2*id,l,m,ind,value);
	else update_tree(2*id+1,m+1,r,ind,value);
	tree[id]=tree[2*id]^tree[2*id+1];
}
int main(){
	int n,m,a,b,c;
	scanf("%d %d",&n,&m);
	for(int i=0;i<n;i++){
		scanf("%lld",&arr[i]);
	}
	build_tree(1,0,n-1);
	while(m--){
		scanf("%d %d %d",&a,&b,&c);
		if(a==2){
			b--;
			c--;
			ll sum=0;
			for(int i=b;i<=c;i++){
				for(int j=i;j<=c;j++){
					sum^=find_xor(1,0,n-1,i,j);
				}
			}
			printf("%lld\n",sum);
		}
		else if(a==1){
			b--;
			update_tree(1,0,n-1,b,c);
		}
	}
	return 0;
}

Compilation message

xoranges.cpp: In function 'int main()':
xoranges.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |  scanf("%d %d",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~
xoranges.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |   scanf("%lld",&arr[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~
xoranges.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |   scanf("%d %d %d",&a,&b,&c);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 24 ms 256 KB Output is correct
5 Correct 25 ms 256 KB Output is correct
6 Execution timed out 1086 ms 384 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1051 ms 8184 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 24 ms 256 KB Output is correct
5 Correct 25 ms 256 KB Output is correct
6 Execution timed out 1086 ms 384 KB Time limit exceeded
7 Halted 0 ms 0 KB -