Submission #1286007

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286007		tuncay_pasha	XORanges (eJOI19_xoranges)	C++20	100 / 100	81 ms	17196 KiB

xoranges

// Try to be as positive as natural numbers :)
#include "bits/stdc++.h"

#define int long long

const int N = 2e5 + 5;

int a[N], b[N];

struct SegTree {
  std::vector<int> st;

  SegTree(int n) {
    st.assign(n * 4, 0);
  }

  void build(int v, int tl, int tr) {
    if (tl == tr) {
      st[v] = a[tl];
      return ;
    }
    int tm = (tl + tr) >> 1;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    st[v] = (st[v * 2] ^ st[v * 2 + 1]);
  }

  void update(int v, int tl, int tr, int i, int x) {
    if (tl == tr) {
      st[v] = x;
      return ;
    }
    int tm = (tl + tr) >> 1;
    if (i <= tm) {
      update(v * 2, tl, tm, i, x);
    } else {
      update(v * 2 + 1, tm + 1, tr, i, x);
    }
    st[v] = (st[v * 2] ^ st[v * 2 + 1]);
  }

  int get(int v, int tl, int tr, int l, int r) {
    if (tr < l || tl > r) {
      return 0;
    } else if (tl >= l && tr <= r) {
      return st[v];
    }
    int tm = (tl + tr) >> 1;
    return (get(v * 2, tl, tm, l, r) ^ get(v * 2 + 1, tm + 1, tr, l, r));
  }
};

signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  int n, q;
  std::cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
    b[i] = a[i];
  }
  for (int i = 1; i <= n; ++i) {
    a[i] = (i & 1 ? a[i] : 0);
  }
  SegTree stOdd(n);
  stOdd.build(1, 1, n);
  for (int i = 1; i <= n; ++i) {
    a[i] = (i & 1 ? 0 : b[i]);
  }
  SegTree stEven(n);
  stEven.build(1, 1, n);
  while (q--) {
    int t;
    std::cin >> t;
    if (t == 1) {
      int i, x;
      std::cin >> i >> x;
      if (i & 1) {
        stOdd.update(1, 1, n, i, x);
      } else {
        stEven.update(1, 1, n, i, x);
      }
    } else {
      int l, r;
      std::cin >> l >> r;
      if (!((r - l + 1) & 1)) {
        std::cout << 0 << '\n';
        continue;
      }
      int ans = (l & 1 ? stOdd.get(1, 1, n, l, r) : stEven.get(1, 1, n, l, r));
      std::cout << ans << '\n';
    }
  }
}

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