Submission #253380

#	Time	Username	Problem	Language	Result	Execution time	Memory
253380		tomek_plywacz	XORanges (eJOI19_xoranges)	C++17	100 / 100	153 ms	10488 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
int t[1000*1000+10];
const int SS = 1024*1024;
int drzewo[SS*2+10];
int drzewo2[SS*2+10];
void Insert(int x, int ind)
{
	if(ind % 2 == 0)
		return;
	ind += SS;
	drzewo[ind] = x;
	ind = (ind>>1);
	while(ind > 0)
	{
		drzewo[ind] = drzewo[(ind<<1)] ^ drzewo[(ind << 1) + 1];
		ind = (ind>>1);
	}
}
int Query(int pocz, int kon)
{
	pocz += SS -1, kon += SS + 1;
	int wynik = 0;
	while((pocz>>1) != (kon>>1))
	{
		if(pocz % 2 == 0)
			wynik = wynik ^ drzewo[pocz+1];
		if(kon%2 == 1)
			wynik = wynik ^ drzewo[kon-1];
		pocz = (pocz>>1), kon = (kon>>1);
	}
	return wynik;
}
void Insert2(int x, int ind)
{
	if(ind % 2 == 1)
		return;
	ind += SS;
	drzewo2[ind] = x;
	ind = (ind>>1);
	while(ind > 0)
	{
		drzewo2[ind] = drzewo2[(ind<<1)] ^ drzewo2[(ind << 1) + 1];
		ind = (ind>>1);
	}
}
int Query2(int pocz, int kon)
{
	pocz += SS -1, kon += SS + 1;
	int wynik = 0;
	while((pocz>>1) != (kon>>1))
	{
		if(pocz % 2 == 0)
			wynik = wynik ^ drzewo2[pocz+1];
		if(kon%2 == 1)
			wynik = wynik ^ drzewo2[kon-1];
		pocz = (pocz>>1), kon = (kon>>1);
	}
	return wynik;
}
int main()
{
	ios_base::sync_with_stdio(0),cin.tie(0);
	int n;
	cin >> n;
	int q;
	cin >> q;
	for(int i = 1; i <= n; i++)
	{
		cin >> t[i];
		Insert(t[i],i);
		Insert2(t[i],i);
	}
	for(int i = 1; i <= q; i++)
	{
		int a,b,c;
		cin >> a >> b >> c;
		if(a == 2)
		{
			if((b-c + 1) % 2 == 0)
				cout << 0 << "\n";
			else
			{
				if(b % 2 == 0)
					cout << Query2(b,c) << "\n";
				else
					cout << Query(b,c) << "\n";
			}
		}
		else
		{
			Insert2(c,b);
			Insert(c,b);
		}
	}
}

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 25 / 25
• Subtask 4: 20 / 20
• Subtask 5: 25 / 25