oj.uz

Submission #752771

# Submission time Handle Problem Language Result Execution time Memory
752771 2023-06-03T20:20:50 Z emad234 XORanges (eJOI19_xoranges) C++17
100 / 100
 635 ms 15688 KB 
#include <bits/stdc++.h>
#define all(v) ((v).begin(),(v).end())
typedef long long ll;
using namespace std;
const ll mod = 1e9 + 7;
const ll mxN = 4e6 + 5;
struct tree{
  ll odd,even,size;
};
tree seg[mxN] = {};
ll N,s,e,val;
tree combine(tree a,tree b){
  tree c;
  c.size = a.size + b.size;
  if(a.size % 2){
    c.odd = (a.odd ^ b.even);
    c.even = (a.even ^ b.odd);
  }else{
    c.odd = (a.odd ^ b.odd);
    c.even = (a.even ^ b.even);
  }
  return c;
}
tree query(ll l = 1,ll r = N,ll ind = 1){
  if(l > e || r < s) return {0,0,0};
  if(l >= s && r <= e) return seg[ind];
  ll md = (l + r) / 2;
  return combine(query(l,md,ind * 2),query(md + 1,r,ind * 2 + 1));
}
void update(ll ind){
  ind += N;
  seg[ind] = {val,0,1};
  ind /= 2;
  while(ind){
    seg[ind] = combine(seg[ind * 2],seg[ind * 2 + 1]);
    ind /= 2;
  }
}
signed main() {
  ll n,q;
  cin >>n>>q;
  N = exp2(ceil(log2(n)));
  for(ll i = 0;i < n;i++){
    cin >>val;
    update(i);
  }
  while(q--){
    ll op,i,j;
    cin >>op>>i>>j;
    if(op == 1){
      val = j;
      i--;
      update(i);
    }else{
      s = i;e = j;
      ll ans =query().odd;
      if((j - i + 1) % 2 == 0) ans = 0;
      cout<<ans<<'\n';
    }
  }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 14 ms 540 KB Output is correct
12 Correct 10 ms 468 KB Output is correct
13 Correct 13 ms 596 KB Output is correct
14 Correct 13 ms 596 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 10864 KB Output is correct
2 Correct 605 ms 15644 KB Output is correct
3 Correct 635 ms 15688 KB Output is correct
4 Correct 558 ms 15532 KB Output is correct
5 Correct 548 ms 15420 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 212 KB Output is correct
7 Correct 2 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 2 ms 212 KB Output is correct
10 Correct 2 ms 212 KB Output is correct
11 Correct 14 ms 540 KB Output is correct
12 Correct 10 ms 468 KB Output is correct
13 Correct 13 ms 596 KB Output is correct
14 Correct 13 ms 596 KB Output is correct
15 Correct 596 ms 10864 KB Output is correct
16 Correct 605 ms 15644 KB Output is correct
17 Correct 635 ms 15688 KB Output is correct
18 Correct 558 ms 15532 KB Output is correct
19 Correct 548 ms 15420 KB Output is correct
20 Correct 497 ms 15440 KB Output is correct
21 Correct 450 ms 15436 KB Output is correct
22 Correct 441 ms 15568 KB Output is correct
23 Correct 525 ms 15464 KB Output is correct
24 Correct 588 ms 15380 KB Output is correct