oj.uz

Submission #1097974

# Submission time Handle Problem Language Result Execution time Memory
1097974 2024-10-08T17:34:00 Z omar1312 XORanges (eJOI19_xoranges) C++17
55 / 100
 1000 ms 8144 KB 
#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

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

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 476 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 476 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 4 ms 604 KB Output is correct
12 Correct 5 ms 604 KB Output is correct
13 Correct 8 ms 592 KB Output is correct
14 Correct 8 ms 604 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1055 ms 8144 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 476 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 4 ms 604 KB Output is correct
12 Correct 5 ms 604 KB Output is correct
13 Correct 8 ms 592 KB Output is correct
14 Correct 8 ms 604 KB Output is correct
15 Execution timed out 1055 ms 8144 KB Time limit exceeded
16 Halted 0 ms 0 KB -