Submission #1219216

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219216		lukasuliashvili	XORanges (eJOI19_xoranges)	C++20	100 / 100	375 ms	11368 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, a, b) for (int i = a; i <= b; i++)
const int N = 2 * 1e5 + 5; // n is up to 2e5, so this is enough
int seg[4 * N], seg2[4 * N], a[N];

void update(int node, int l, int r, int idx, int u) {
	if (l == r) {
		seg[node] = u;
		return;
	}
	int m = (l + r) / 2;
	if (idx <= m)
		update(2 * node, l, m, idx, u);
	else
		update(2 * node + 1, m + 1, r, idx, u);
	seg[node] = seg[2 * node] ^ seg[2 * node + 1];
}

void update2(int node, int l, int r, int idx, int u) {
	if (l == r) {
		seg2[node] = u;
		return;
	}
	int m = (l + r) / 2;
	if (idx <= m)
		update2(2 * node, l, m, idx, u);
	else
		update2(2 * node + 1, m + 1, r, idx, u);
	seg2[node] = seg2[2 * node] ^ seg2[2 * node + 1];
}

int get(int node, int l, int r, int s, int e) {
	if (l > e || r < s)
		return 0;
	if (l >= s && r <= e)
		return seg[node];
	int m = (l + r) / 2;
	int val1 = get(2 * node, l, m, s, e);
	int val2 = get(2 * node + 1, m + 1, r, s, e);
	return val1 ^ val2;
}

int get1(int node, int l, int r, int s, int e) {
	if (l > e || r < s)
		return 0;
	if (l >= s && r <= e)
		return seg2[node];
	int m = (l + r) / 2;
	int val1 = get1(2 * node, l, m, s, e);
	int val2 = get1(2 * node + 1, m + 1, r, s, e);
	return val1 ^ val2;
}

signed main() {
	int n, q;
	cin >> n >> q;
	rep(i, 1, n) {
		cin >> a[i];
		update(1, 1, n, i, a[i]);
		if (i % 2 == 1)
			update2(1, 1, n, i, a[i]);
	}
	rep(i, 1, q) {
		int type;
		cin >> type;
		if (type == 2) {
			int l, r;
			cin >> l >> r;
			if ((r - l + 1) % 2 == 0) {
				cout << 0 << endl;
			} else {
				int val1 = get(1, 1, n, l, r);
				int val2 = get1(1, 1, n, l, r);
				if (l % 2 == 1) {
					cout << val2 << endl;
				} else {
					cout << (val1 ^ val2) << endl;
				}
			}
		} else {
			int l, u;
			cin >> l >> u;
			update(1, 1, n, l, u);
			if (l % 2 == 1)
				update2(1, 1, n, l, u);
		}
	}
}

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