Submission #1097974

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097974		omar1312	XORanges (eJOI19_xoranges)	C++17	55 / 100	1055 ms	8144 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 = 200005;
// blocks size nvm because even
ll a[N+2], dp[N+2];
//   odd  even
pair<int, int> sq[N+2][33];
void solve(){
	int n, q;
	cin>>n>>q;
	ll cnt = 0;
	ll sqrtn = sqrt(n);
	for(int i = 1; i <= n; i++){
		cin>>a[i];
		for(int j = 0; j < 32; j++){
			if(i % 2 == 0)sq[i/sqrtn][j].second += (((1 << j) & a[i]) >= 1);
			else sq[i/sqrtn][j].first += (((1 << j) & a[i]) >= 1);
		}
	}
	while(q--){
		int type;
		cin>>type;
		if(type == 1){
			// update;
			int u, v;
			cin>>u>>v;
			for(int j = 0; j < 32; j++){
				if(u % 2 == 1)sq[u/sqrtn][j].first -= (((1 << j) & a[u]) >= 1), sq[u/sqrtn][j].first += (((1 << j) & v) >= 1);
				else sq[u/sqrtn][j].second -= (((1 << j) & a[u]) >= 1), sq[u/sqrtn][j].second += (((1 << j) & v) >= 1);
			}
			a[u] = v;
			// all good
		}
		else{
			int l, r;
			cin>>l>>r;
			ll tmp[33] = {};
			ll ans = 0;
			if((r - l + 1) % 2 == 0){
				cout<<0<<'\n';
				continue;
			}
			if(r - l + 1 < sqrtn){
				// do loop
				for(int i = l, k = 1; i <= r; i++, k++){
					for(int j = 0; j < 32; j++){
						tmp[j] += (((1 << j) & a[i]) >= 1) * (r - l + 1 - k + 1) * k;
					}
				}
				for(int j = 0; j < 32; j++){
					if(tmp[j] % 2 == 1)ans |= (1 << j);
				}
				cout<<ans<<'\n';
				continue;
			}
			bool odd = (l % 2 == 1);
			for(int i = l/sqrtn+1; i < r/sqrtn; i++){
				for(int j = 0; j < 32; j++){
					if(odd)tmp[j] += sq[i][j].first;
					else tmp[j] += sq[i][j].second;
				}
			}
			for(int i = l; i < (l/sqrtn+1) * sqrtn; i++){
				if(i % 2 == odd){
					for(int j = 0; j < 32; j++){
						tmp[j] += (((1 << j) & a[i]) >= 1);
					}
				}
			}
			for(int i = (r/sqrtn)*sqrtn; i <= r; i++){
				if(i % 2 == odd){
					for(int j = 0; j < 32; j++){
						tmp[j] += (((1 << j) & a[i]) >= 1);
					}
				}
			}
			for(int j = 0; j < 32; j++){
				if(tmp[j] % 2 == 1)ans |= (1 << j);
			}
			cout<<ans<<'\n';
		}
	}
}
int main(){
cin.tie(0)->sync_with_stdio(0);
	int tt = 1;
	// cin>>tt;
	while(tt--){
		solve();
		// cout<<'\n';
	}
}

Compilation message (stderr)

xoranges.cpp: In function 'void solve()':
xoranges.cpp:19:5: warning: unused variable 'cnt' [-Wunused-variable]
   19 |  ll cnt = 0;
      |     ^~~

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