Submission #1071587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071587		DariusH	XORanges (eJOI19_xoranges)	C++14	100 / 100	368 ms	7884 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

#define N_MAX 200001
int v[N_MAX / 2 + 1][2], aib[N_MAX / 2 + 1][2];

void update(int pos, int newval, int p, int n) {
  int oldval = v[pos][p];
  v[pos][p] = newval;
  while(pos <= n) {
    aib[pos][p] ^= oldval;
    aib[pos][p] ^= newval;
    pos += (pos & (-pos));
  }
}

int query(int pos, int p, int n) {
  int res = 0;
  while(pos > 0) {
    res ^= aib[pos][p];
    pos -= (pos & (-pos));
  }

  return res;
}

int main()
{
  int q, i, t, a, b, val, n;
  cin >> n >> q;
  for(i = 1; i <= n; ++i) {
    cin >> val;
    if(i % 2 == 0) {
      update(i / 2, val, 1, n / 2);
    }else{
      update(i / 2 + 1, val, 0, n / 2 + n % 2);
    }
  }

  while(q--) {
    cin >> t >> a >> b;
    if(t == 1) {
      if(a % 2 == 0) {
        update(a / 2, b, 1, n / 2);
      }else{
        update(a / 2 + 1, b, 0, n / 2 + n % 2);
      }
    }else{
      if((b - a) % 2 == 1) {
        cout << "0\n";
      }else{
        if(a % 2 == 0) {
          if(b % 2 == 1) {
            --b;
          }
          cout << (query(b / 2, 1, n / 2) ^ query((a - 1) / 2, 1, n / 2)) << '\n';
        }else{
          if(b % 2 == 0) {
            --b;
          }
          cout << (query(b / 2 + 1, 0, n / 2 + n % 2) ^ query((a - 1) / 2, 0, n / 2 + n % 2)) << '\n';
        }
      }

    }
  }

  return 0;
}

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