Submission #1195345

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195345		Johan	XORanges (eJOI19_xoranges)	C++20	100 / 100	156 ms	10460 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
  
const int MAX = 3e5 + 6;
const int LOG = 26;
const int inf = 1e18;
const int mod = 1e9 + 7;
const int block = 320;
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int st_t[MAX * 4], st_c[MAX * 4];
void upd_t(int v, int l, int r, int pos, int val){
	if(l == r){
		st_t[v] = val;
		return;
	}
	int mid = (l + r) >> 1;
	if(mid >= pos)
		upd_t(v * 2, l, mid, pos, val);
	else
		upd_t(v * 2 + 1, mid + 1, r, pos, val);
	st_t[v] = (int)(st_t[v * 2] ^ st_t[v * 2 + 1]);
}
void upd_c(int v, int l, int r, int pos, int val){
	if(l == r){
		st_c[v] = val;
		return;
	}
	int mid = (l + r) >> 1;
	if(mid >= pos)
		upd_c(v * 2, l, mid, pos, val);
	else
		upd_c(v * 2 + 1, mid + 1, r, pos, val);
	st_c[v] = (int)(st_c[v * 2] ^ st_c[v * 2 + 1]);
}
int ask_t(int v, int l, int r, int ql, int qr){
	if(l > qr || r < ql)	return 0;
	if(l >= ql && r <= qr)	return st_t[v];
	int mid = (l + r) >> 1;
	return (int)(ask_t(v * 2, l, mid, ql, qr) ^ ask_t(v * 2 + 1, mid + 1, r, ql, qr));
}
int ask_c(int v, int l, int r, int ql, int qr){
	if(l > qr || r < ql)	return 0;
	if(l >= ql && r <= qr)	return st_c[v];
	int mid = (l + r) >> 1;
	return (int)(ask_c(v * 2, l, mid, ql, qr) ^ ask_c(v * 2 + 1, mid + 1, r, ql, qr));
}
void _(){
	int n, q;
	cin >> n >> q;
	vector < int > a(n + 1);
	vector < int > T(n + 1);
	vector < int > C(n + 1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		if(i & 1)
			T[i / 2 + 1] = a[i];
		else
			C[i / 2] = a[i];
	}
	int sz_t = n / 2 + n % 2;
	for(int i = 1; i <= sz_t; i++)
		upd_t(1, 1, sz_t, i, T[i]);
	int sz_c = n / 2;
	for(int i = 1; i <= sz_c; i++)
		upd_c(1, 1, sz_c, i, C[i]);
	while(q--){
		int type;
		cin >> type;
		if(type == 1){
			int pos, val;
			cin >> pos >> val;
			if(pos & 1)
				upd_t(1, 1, sz_t, pos / 2 + 1, val);
			else
				upd_c(1, 1, sz_c, pos / 2, val);
		}
		else {
			int l, r;
			cin >> l >> r;
			if((r - l) % 2 == 1){
				cout << 0 << endl;
				continue;
			}
			if(l % 2 == 0){
				l = l / 2;
				r = r / 2;
				cout << ask_c(1, 1, sz_c, l, r) << "\n";
			}
			else {
				l = l / 2 + 1;	
				r = r / 2 + 1;
				cout << ask_t(1, 1, sz_t, l, r) << "\n";
			}
		}
	}
}
 
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t = 1;
//	cin >> t;
	while(t--)  _();
}

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