Submission #603709

#	Time	Username	Problem	Language	Result	Execution time	Memory
603709		Lextyle	XORanges (eJOI19_xoranges)	C++17	100 / 100	124 ms	13292 KiB

xoranges

#include <bits/stdc++.h>
#pragma warning(disable : 4996)
#pragma warning(disable : 6031)
#define USACO freopen("clumsy.in", "r", stdin); freopen("clumsy.out", "w+", stdout);    
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
pair<int, pair<int, int>> segtree[600000];
int a[300000];

void build(int node, int l, int r) {
	if (r - l + 1 == 1) {
		segtree[node].first = a[l];
		segtree[node].second.first = a[l];
		return;
	}
	int mid = l + (r - l + 1) / 2;
	build(node * 2, l, mid - 1);
	build(node * 2 + 1, mid, r);
	if (r - l + 1 == 2) {
		segtree[node].first = segtree[node * 2].first ^ segtree[node * 2 + 1].first;
		segtree[node].second.first = segtree[node * 2].first;
		segtree[node].second.second = segtree[node * 2 + 1].first;
		return;
	}
	segtree[node].first = segtree[node * 2].first ^ segtree[node * 2 + 1].first;
	segtree[node].second.first = segtree[node * 2].second.first ^ segtree[node * 2 + 1].second.first;
	segtree[node].second.second = segtree[node * 2].second.second ^ segtree[node * 2 + 1].second.second;
}

void change(int node, int l, int r, int i, int x) {
	if (r - l + 1 == 1) {
		segtree[node].first = x;
		segtree[node].second.first = x;
		return;
	}
	int mid = l + (r - l + 1) / 2;
	if (i < mid) change(node * 2, l, mid - 1, i, x);
	else  change(node * 2 + 1, mid, r, i, x);
	if (r - l + 1 == 2) {
		segtree[node].first = segtree[node * 2].first ^ segtree[node * 2 + 1].first;
		segtree[node].second.first = segtree[node * 2].first;
		segtree[node].second.second = segtree[node * 2 + 1].first;
		return;
	}
	segtree[node].first = segtree[node * 2].first ^ segtree[node * 2 + 1].first;
	segtree[node].second.first = segtree[node * 2].second.first ^ segtree[node * 2 + 1].second.first;
	segtree[node].second.second = segtree[node * 2].second.second ^ segtree[node * 2 + 1].second.second;
}

int getxor(int node, int l, int r, int lq, int rq) {
	if (l >= lq && r <= rq)
		if ((l - lq + 1) % 2) return segtree[node].second.first;
		else return segtree[node].second.second;
	else if (r < lq || l > rq) return 0;
	else {
		int mid = l + (r - l + 1) / 2;
		return getxor(node * 2, l, mid - 1, lq, rq) ^ getxor(node * 2 + 1, mid, r, lq, rq);
	}
}

int main() {
	//USACO;
	fastIO;
	int n, q;
	cin >> n >> q;
	for (int i = 0; i < n; i++) cin >> a[i];
	int newn = 1;
	while (newn < n) newn <<= 1;
	n = newn;
	build(1, 0, n - 1);
	while (q--) {
		int i;
		cin >> i;
		if (i == 1) {
			int j, x;
			cin >> j >> x; j--;
			change(1, 0, n - 1, j, x);
		}
		else {
			int l, r;
			cin >> l >> r; l--; r--;
			if ((r - l + 1) % 2 == 0) cout << "0\n";
			else cout << getxor(1, 0, n - 1, l, r) << "\n";
		}
	}
}

Compilation message (stderr)

xoranges.cpp:2: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    2 | #pragma warning(disable : 4996)
      | 
xoranges.cpp:3: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    3 | #pragma warning(disable : 6031)
      |

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