Submission #463570

#	Time	Username	Problem	Language	Result	Execution time	Memory
463570		Elias	XORanges (eJOI19_xoranges)	C++17	100 / 100	291 ms	29780 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

#define int long long

struct XORange
{
	int size;	 // the size of the range
	int xorEven; // the xor of all even elements in range
	int xorOdd;	 // the xor of all odd elemements in range

	XORange operator+(XORange other)
	{
		if (size % 2) // if size of current range is odd, the even / odd of other range gets swapped
			swap(other.xorEven, other.xorOdd);
		return {size + other.size, other.xorEven ^ xorEven, other.xorOdd ^ xorOdd};
	}
};
const XORange neutral{0, 0, 0};

vector<XORange> a;
vector<XORange> b;

XORange segInit(int l, int r, int i)
{
	if (l + 1 == r)
		return b[i] = a[l];
	int m = (l + r) / 2;
	return b[i] = segInit(l, m, i * 2 + 1) + segInit(m, r, i * 2 + 2);
}

XORange segGet(int l, int r, int i, int qL, int qR)
{
	if (r <= qL || qR <= l) // out of range
		return neutral;
	if (qL <= l && r <= qR) // completely within range
		return b[i];
	int m = (l + r) / 2;
	return segGet(l, m, i * 2 + 1, qL, qR) + segGet(m, r, i * 2 + 2, qL, qR);
}

XORange segSet(int l, int r, int i, int k, XORange x)
{
	if (!(l <= k && k < r))
		return b[i];
	if (l + 1 == r)
		return b[i] = a[k] = x;
	int m = (l + r) / 2;
	return b[i] = segSet(l, m, i * 2 + 1, k, x) + segSet(m, r, i * 2 + 2, k, x);
}

signed main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);

	int n, q;
	cin >> n >> q;

	a = vector<XORange>(n);
	b = vector<XORange>(n * 4);

	for (int i = 0; i < n; i++)
	{
		int x;
		cin >> x;
		a[i] = {1, x, 0};
	}

	segInit(0, n, 0);

	while (q--)
	{
		int t;
		cin >> t;
		if (t == 1)
		{ // update
			int k, x;
			cin >> k >> x;
			k--; // stupid 1 based indexing
			segSet(0, n, 0, k, {1, x, 0});
		}
		else
		{
			int l, r;
			cin >> l >> r;
			l--; // stupid 1 based indexing
			auto range = segGet(0, n, 0, l, r);
			if (range.size % 2)
				cout << range.xorEven << "\n";
			else
				cout << "0\n";
		}
	}
}

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