Submission #1123927

#	Time	Username	Problem	Language	Result	Execution time	Memory
1123927		ZyadH1	XORanges (eJOI19_xoranges)	C++20	100 / 100	183 ms	10396 KiB

xoranges

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx,avx2,fma")

using namespace std;

#define int long long
#define endl '\n'
const int mxn = 200001;
struct seg{
  int odd = 0;
  int even = 0;
  seg & operator ^= (seg a) {odd = a.odd ^ odd ; even = a.even ^ even; return *this;}
  friend seg operator ^ (seg a , seg b) {return a ^= b;}
  int res(seg a){
    return a.odd ^ a.even;
  }
} XOR[1 << (int)(ceil(log2(mxn))) + 1];
int N = 1 << (int)(ceil(log2(mxn)));
int a[mxn];
int l , r;
seg query(int i = 1 , int lo = 0 , int hi = N - 1){
    if(lo >= l and hi <= r){
      return XOR[i];
    }
    if(lo > r or hi < l) return {0 , 0};
    return query(i * 2 , lo , (lo + hi) / 2) ^ query(i * 2 + 1 , (lo + hi) / 2 + 1 , hi);
}
void update(int i){
  i /= 2;
  while(i){
    XOR[i] = XOR[i * 2] ^ XOR[i * 2 + 1];
    i /= 2;
  }
}
signed main(){
    cin.tie(0) -> sync_with_stdio(0);
    int n , q;
    cin >> n >> q;
    for(int i = 0 ; i < n; i++){
      cin >> a[i];
      if(i % 2){
        XOR[i + N].even = a[i];
      }
      else{
        XOR[i + N].odd = a[i];
      }
    }
    for(int i = N - 1; i >= 0 ; i--){
      XOR[i] = XOR[i * 2] ^ XOR[i * 2 + 1];
    }
    while(q--){
      int t;
      cin >> t;
      if(t == 1){
        int idx , val;
        cin >> idx >> val;
        if(idx % 2){
          XOR[idx - 1 + N].odd = val;

        }
        else {
          XOR[idx - 1 + N].even = val;
        }
        update(idx - 1 + N);
      }
      else {
        cin >> l >> r;
        l --;
        r --;
        seg Q = query();
        if((r - l + 1) % 2 == 0){
          cout <<0 << endl;
        }
        else {
          if((l + 1) % 2){
            cout << Q.odd << endl;
          }
          else cout  << Q.even << endl;
        }
      }
    }
    // cout << XOR[N].odd << " " << XOR[N].even << endl;
    // cout << XOR[N + 1].odd << " " << XOR[N + 1].even << endl;
    // cout << XOR[N + 2].odd << " " << XOR[N + 2].even << endl;

}

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