Submission #305513

#	Time	Username	Problem	Language	Result	Execution time	Memory
305513		danitro	XORanges (eJOI19_xoranges)	C++14	0 / 100	1055 ms	6532 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;

#define MAX 4 * 2100000

int n, q, a, e, w, trr[MAX], trl[MAX];

vector<int> ll, rr;

void buil(int v, int l, int r)
{
	//cout << l << " " << r << endl;
	if(l == r)
	{
		if(r < int(ll.size()))trl[v] = ll[r];
		return;
	}	
	int mid = (l + r) / 2;
	buil(v * 2, l, mid);
	buil(v * 2 + 1, mid + 1, r);
	trl[v] = trl[v * 2] ^trl[v * 2 + 1];
	return; 
}

void buir(int v, int l, int r)
{
	if(l == r)
	{
		if(l < int(rr.size()))trr[v] = rr[l];
		return;
	}	
	int mid = (l + r) / 2;
	buir(v * 2, l, mid);
	buir(v * 2 + 1, mid + 1, r);
	trr[v] = trr[v * 2] ^trr[v * 2 + 1];
	return; 
}

int qur(int v, int l, int r, int ql, int qr)
{
	if(l > qr || r < ql)return 0;
	if(l >= ql && r <= qr)
	{
	//	cout << l << " " << r << "  "<< v << " " << trr[v] << "  " << trr[v * 2] << "  " << trr[v * 2 + 1]<< endl;
		return trr[v];
	}
	int mid = (l + r) / 2;
	return qur(v * 2, l, mid, ql, qr) ^ qur(v * 2 + 1, mid + 1, r, ql, qr);
}

int qul(int v, int l, int r, int ql, int qr)
{
	
	if(l > qr || r < ql)return 0;
	if(l >= ql && r <= qr)return trl[v];
	int mid = (l + r) / 2;
	return qul(v * 2, l, mid, ql, qr) ^ qul(v * 2 + 1, mid + 1, r, ql, qr);
}

void upr(int v, int l, int r, int ql, int val)
{
	if(l > ql || r < ql)return;
	if(l == ql && r == ql)
	{
		
		trr[v] = val;
		return;
	}
	int mid = (l + r) / 2;
	upr(v * 2, l, mid, ql, val);
	upr(v * 2 + 1, mid + 1, r, ql, val);
	trr[v] = trr[v * 2] ^ trr[v * 2 + 1];
}

void upl(int v, int l, int r, int ql, int val)
{
	if(l > ql || r < ql)return;
	if(l == ql && r == ql)
	{
		trl[v] = val;
		return;
	}
	int mid = (l +r) / 2;
	upl(v * 2, l, mid, ql, val);
	upl(v * 2 + 1, mid + 1, r, ql, val);
	trl[v] = trl[v * 2] ^ trl[v * 2 + 1];
}


int main()
{
	cin >> n >> q;
	ll.push_back(0);
	rr.push_back(0);
	for(int i = 1;i <= n; i++)
	{
		cin >> a;
		if(i % 2 == 0)ll.push_back(a);
		else rr.push_back(a);
	}
	
	buil(1, 1, 210000);
	buir(1, 1, 210000);
	
	for(int i = 0; i < q; i++)
	{
		cin >> a >> e >> w;
		if(a == 2)
		{
			if((e - w) % 2 == 1)cout << "0\n";
			else
			{
				if(e % 2 == 0)cout << qul(1, 1, 210000, e / 2, w / 2) << endl;
				else  cout << qur(1, 1, 210000, e / 2  + 1, w / 2 + 1) << endl;
				//cout << e/2 << " " <<  w/2<< endl;
			}
		}
		else
		{
			if(e % 2 == 0)upl(1, 1, 210000, e / 2, w) ;
			else upr(1, 1, 210000, e / 2  + 1, w);
		}
	}
	//cout << trr[0] << endl;
	return 0;
}

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