oj.uz

Submission #966225

# Submission time Handle Problem Language Result Execution time Memory
966225 2024-04-19T14:34:44 Z vjudge1 XORanges (eJOI19_xoranges) C++17
100 / 100
 437 ms 14308 KB 
#include<bits/stdc++.h>
using namespace std;
long long n,q,a[1000001],b[1000001],c[1000001],tc[4000001],tl[4000001],db=1,dc=1;
void build(long long id,long long l,long long r)
{
	if(l==r)
	{
		if(l%2==0)
		{
			tc[id]=a[l];
			tl[id]=0;
		}
		else
		{
			tc[id]=0;
			tl[id]=a[l];
		}
		return ;
	}
	long long mid=(l+r)/2;
	build(id*2,l,mid);
	build(id*2+1,mid+1,r);
	tc[id]=tc[id*2]^tc[id*2+1];
	tl[id]=tl[id*2]^tl[id*2+1];
}
void update(long long id,long long l,long long r ,long long pos,long long w)
{
	if(l>pos||r<pos) return ;
	if(l==r)
	{
		if(l%2==1)
		{
//			tl[id]=a[pos];
			tl[id]=w;
			return ;
		}
		else
		{
//			tc[id]=a[pos];
			tc[id]=w;
			return ;
		}
	}
	long long mid=(l+r)/2;
	update(id*2,l,mid,pos,w);
	update(id*2+1,mid+1,r,pos,w);
	tc[id]=tc[id*2]^tc[id*2+1];
	tl[id]=tl[id*2]^tl[id*2+1];
}
long long getc(long long id,long long l,long long r,long long u,long long v)
{
	if(l>v||r<u) return 0;
	if(u<=l&&r<=v)
	{
		return tc[id];
	}
	long long mid=(l+r)/2;
	return getc(id*2,l,mid,u,v)^getc(id*2+1,mid+1,r,u,v);
}
long long getl(long long id,long long l,long long r,long long u,long long v)
{
	if(l>v||r<u) return 0;
	if(u<=l&&r<=v)
	{
//		cout<<l<<" "<<r<<endl;
		return tl[id];
	}
	long long mid=(l+r)/2;
	return getl(id*2,l,mid,u,v)^getl(id*2+1,mid+1,r,u,v);
}

int main()
{
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	while(q--)
	{
		long long tv;
		cin>>tv;
		if(tv==1)
		{
			long long pos,w;
			cin>>pos>>w;
			a[pos]=w;
			update(1,1,n,pos,w);
		}
		else
		{
			long long l,r;
			cin>>l>>r;
			if((r-l)%2==1)
			{
				cout<<0<<endl;
			}
			else
			{
				if(l%2==1)
				{
					cout<<getl(1,1,n,l,r)<<endl;
				}
				else cout<<getc(1,1,n,l,r)<<endl;
			}
		}
	}
	return 0;	
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4440 KB Output is correct
2 Correct 2 ms 4440 KB Output is correct
3 Correct 2 ms 4440 KB Output is correct
4 Correct 2 ms 4440 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 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4440 KB Output is correct
7 Correct 2 ms 4440 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 2 ms 4440 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 8 ms 4444 KB Output is correct
12 Correct 8 ms 4440 KB Output is correct
13 Correct 11 ms 4696 KB Output is correct
14 Correct 11 ms 4700 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 437 ms 14012 KB Output is correct
2 Correct 431 ms 13908 KB Output is correct
3 Correct 436 ms 13908 KB Output is correct
4 Correct 420 ms 14308 KB Output is correct
5 Correct 422 ms 13908 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4440 KB Output is correct
3 Correct 2 ms 4444 KB Output is correct
4 Correct 1 ms 4444 KB Output is correct
5 Correct 2 ms 4444 KB Output is correct
6 Correct 2 ms 4440 KB Output is correct
7 Correct 2 ms 4440 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 2 ms 4440 KB Output is correct
10 Correct 2 ms 4444 KB Output is correct
11 Correct 8 ms 4444 KB Output is correct
12 Correct 8 ms 4440 KB Output is correct
13 Correct 11 ms 4696 KB Output is correct
14 Correct 11 ms 4700 KB Output is correct
15 Correct 437 ms 14012 KB Output is correct
16 Correct 431 ms 13908 KB Output is correct
17 Correct 436 ms 13908 KB Output is correct
18 Correct 420 ms 14308 KB Output is correct
19 Correct 422 ms 13908 KB Output is correct
20 Correct 340 ms 13484 KB Output is correct
21 Correct 326 ms 13468 KB Output is correct
22 Correct 341 ms 13396 KB Output is correct
23 Correct 405 ms 14000 KB Output is correct
24 Correct 412 ms 13992 KB Output is correct