Submission #983528

#	Time	Username	Problem	Language	Result	Execution time	Memory
983528		Nomio	XORanges (eJOI19_xoranges)	C++17	100 / 100	116 ms	11624 KiB

xoranges

#include <bits/stdc++.h>
#define meta int tm = tl + (tr - tl) / 2, x = (i << 1) + 1, y = x + 1
using namespace std;
int st1[800001] {}, st2[800001] {};

void update1(int i, int tl, int tr, int l, int v) {
	if(tl == tr) {
		st1[i] = v;
		return;
	}
	meta;
	if(l <= tm) {
		update1(x, tl, tm, l, v);
	} else {
		update1(y, tm + 1, tr, l, v);
	}
	st1[i] = (st1[x] ^ st1[y]);
}

void update2(int i, int tl, int tr, int l, int v) {
	if(tl == tr) {
		st2[i] = v;
		return;
	}
	meta;
	if(l <= tm) {
		update2(x, tl, tm, l, v);
	} else {
		update2(y, tm + 1, tr, l, v);
	}
	st2[i] = (st2[x] ^ st2[y]);
}

int query1(int i, int tl, int tr, int l, int r) {
	if(l <= tl && tr <= r) {
		return st1[i];
	}
	meta;
	if(r <= tm) {
		return query1(x, tl, tm, l, r);
	} else if(l > tm) {
		return query1(y, tm + 1, tr, l, r);
	} else {
		return (query1(x, tl, tm, l, tm) ^ query1(y, tm + 1, tr, tm + 1, r));
	}
}

int query2(int i, int tl, int tr, int l, int r) {
	if(l <= tl && tr <= r) {
		return st2[i];
	}
	meta;
	if(r <= tm) {
		return query2(x, tl, tm, l, r);
	} else if(l > tm) {
		return query2(y, tm + 1, tr, l, r);
	} else {
		return (query2(x, tl, tm, l, tm) ^ query2(y, tm + 1, tr, tm + 1, r));
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	for(int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if(i % 2 == 0) {
			update1(0, 0, n - 1, i, a);
		} else {
			update2(0, 0, n - 1, i, a);
		}
	}
	while(q--) {
		int t, l, r;
		cin >> t >> l >> r;
		if(t == 1) {
			l--;
			if(l % 2 == 0) {
				update1(0, 0, n - 1, l, r);	
			} else {
				update2(0, 0, n - 1, l, r);
			}
		} else {
			if((r - l + 1) % 2 == 0) {
				cout << 0 << '\n';
			} else {
				l--;
				r--;
				if(l % 2 == 0) {
					cout << query1(0, 0, n - 1, l, r) << '\n';
				} else {
					cout << query2(0, 0, n - 1, l, r) << '\n';
				}
			}
		}
	}
	return 0;
}

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