oj.uz

Submission #1097968

# Submission time Handle Problem Language Result Execution time Memory
1097968 2024-10-08T17:16:46 Z SulA XORanges (eJOI19_xoranges) C++17
12 / 100
 899 ms 3152 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 446 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 = 446;
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].first += (((1 << j) & a[i]) >= 1);
else sq[i/sqrtn][j].second += (((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 == 0)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;
}
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;
}
for(int i = l/sqrtn+1; i < r/sqrtn; i++){
for(int j = 0; j < 32; j++){
tmp[j] += sq[i][j].first;
}
}
for(int i = l; i < (l/sqrtn+1) * sqrtn; i++){
if(i % 2 == 1){
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 == 1){
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:4: 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 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 2 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 899 ms 3152 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Incorrect 2 ms 344 KB Output isn't correct
7 Halted 0 ms 0 KB -