oj.uz

Submission #463570

# Submission time Handle Problem Language Result Execution time Memory
463570 2021-08-11T10:19:21 Z Elias XORanges (eJOI19_xoranges) C++17
100 / 100
 291 ms 29780 KB 
#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.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 332 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 376 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 5 ms 972 KB Output is correct
12 Correct 5 ms 972 KB Output is correct
13 Correct 5 ms 1020 KB Output is correct
14 Correct 5 ms 972 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 291 ms 24976 KB Output is correct
2 Correct 285 ms 29716 KB Output is correct
3 Correct 285 ms 29780 KB Output is correct
4 Correct 230 ms 29436 KB Output is correct
5 Correct 224 ms 29420 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 376 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 324 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 5 ms 972 KB Output is correct
12 Correct 5 ms 972 KB Output is correct
13 Correct 5 ms 1020 KB Output is correct
14 Correct 5 ms 972 KB Output is correct
15 Correct 291 ms 24976 KB Output is correct
16 Correct 285 ms 29716 KB Output is correct
17 Correct 285 ms 29780 KB Output is correct
18 Correct 230 ms 29436 KB Output is correct
19 Correct 224 ms 29420 KB Output is correct
20 Correct 283 ms 29468 KB Output is correct
21 Correct 279 ms 29656 KB Output is correct
22 Correct 283 ms 29536 KB Output is correct
23 Correct 224 ms 29408 KB Output is correct
24 Correct 228 ms 29528 KB Output is correct