Submission #1011617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011617		ziyad_alharbi	XORanges (eJOI19_xoranges)	C++17	100 / 100	84 ms	9296 KiB

xoranges

#include<bits/stdc++.h>
using namespace std;
const int o = 131072;
vector<int>tr1(o * 2), tr2(o * 2);
void u1(int x, int v)
{
	x += o;
	tr1[x] = v;
	for (x /= 2; x > 0; x /= 2)
	{
		//cout << tr1[x * 2] << ' ' << tr1[x * 2 + 1] << '\n';
		tr1[x] = (tr1[x * 2] ^ tr1[x * 2 + 1]);
	}
}
void u2(int x, int v)
{
	x += o;
	tr2[x] = v;
	for (x /= 2; x > 0; x /= 2)
	{
		//cout << tr2[x * 2] << ' ' << tr2[x * 2 + 1] << '\n';
		tr2[x] = (tr2[x * 2] ^ tr2[x * 2 + 1]);
	}
}
int _q1(int l, int r, int ql, int qr, int v)
{
	if (l >= qr || r <= ql)return 0;
	else if (l >= ql && r <= qr)
	{
		return tr1[v];
	}
	else
	{
		int m = (l + r) / 2;
		int ll = _q1(l, m, ql, qr, v * 2), rr = _q1(m, r, ql, qr, v * 2 + 1);
		//cout << ll << ' ' << rr << '\n';
		return (ll ^ rr);
	}
}
int q1(int l, int r)
{
	return _q1(0, o, l, r, 1);
}
int _q2(int l, int r, int ql, int qr, int v)
{
	if (l >= qr || r <= ql)return 0;
	else if (l >= ql && r <= qr)
	{
		return tr2[v];
	}
	else
	{
		int m = (l + r) / 2;
		int ll = _q2(l, m, ql, qr, v * 2), rr = _q2(m, r, ql, qr, v * 2 + 1);
		//cout << ll << ' ' << rr << '\n';
		return (ll ^ rr);
	}
}
int q2(int l, int r)
{
	return _q2(0, o, l, r, 1);
}
signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t--)
	{
		int n, q;
		cin >> n >> q;
		int a[n + 1];
		for (int x = 0; x < n; x++)
		{
			cin >> a[x];
			if (x % 2)
			{
				u1(x / 2, a[x]);
			}
			else
			{
				u2(x / 2, a[x]);
			}
		}
		while (q--)
		{
			int t, l, r;
			cin >> t >> l >> r;
			l--;
			r--;
			if (t == 1)
			{
				r++;
				if (l % 2)
				{
					u1(l / 2, r);
				}
				else
				{
					u2(l / 2, r);
				}
			}
			else
			{
				if (l % 2 != r % 2)cout << "0\n";
				else if (l % 2)
				{
					cout << q1(l / 2, r / 2 + 1) << '\n';
				}
				else
				{
					cout << q2(l / 2, r / 2 + 1) << '\n';
				}
			}
		}
	}
}

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