Submission #1098107

#	Time	Username	Problem	Language	Result	Execution time	Memory
1098107		omar1312	XORanges (eJOI19_xoranges)	C++17	100 / 100	94 ms	16212 KiB

xoranges

#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
// typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
const int mod = 1000000007;
const int N = 262144;
ll a[N+2];
ll tree[N*2+2][2];
ll query(int node, int L, int R, int l, int r, bool odd){
	if(l > R || r < L)return 0;
	if(l >= L && r <= R){
		return tree[node][odd];
	}
	ll mid = (l + r) / 2;
	return (query(node * 2, L, R, l, mid, odd) ^ query(node * 2 + 1, L, R, mid+1, r, odd));
}
void update(int ind, int node, int n){
	ll old = ind;
	old += n;
	tree[old][ind % 2] = node;
	a[ind] = node;
	old >>= 1;
	while(old){
		tree[old][ind % 2] = tree[old * 2][ind % 2] ^ tree[old * 2 + 1][ind % 2];
		old >>= 1;
	}
	return;
}
void solve(){
	int n, q;
	cin>>n>>q;
	for(int i = 0; i < n; i++){
		cin>>a[i];
	}
	ll off = 1;
	while(off < n)off <<= 1;
	n = off;
	for(int i = 0; i < n; i++){
		tree[i + n][i % 2] = a[i];
	}
	for(int i = n-1; i >= 0; i--){
		tree[i][0] = tree[i * 2][0] ^ tree[i * 2 + 1][0];
		tree[i][1] = tree[i * 2][1] ^ tree[i * 2 + 1][1];
	}
	while(q--){
		int type;
		cin>>type;
		if(type == 1){
			int u, x;
			cin>>u>>x;
			--u;
			update(u, x, n);
		}
		else{
			int l, r;
			cin>>l>>r;
			if((r - l + 1) % 2 == 0){
				cout<<0<<'\n';
				continue;
			}
			--l;
			--r;
			cout<<query(1, l, r, 0, n-1, l % 2)<<'\n';
		}
	}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
	int tt = 1;
	// cin>>tt;
	while(tt--){
		solve();
		cout<<'\n';
	}
}

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