Submission #547213

#	Time	Username	Problem	Language	Result	Execution time	Memory
547213		vlad_TT	XORanges (eJOI19_xoranges)	C++17	100 / 100	517 ms	9228 KiB

xoranges

#include <iostream>

const int MAX_N = 2 * 1e5;
int a[2][1 + MAX_N / 2], aint[2][1 + 4 * MAX_N];

void buildPar(int v, int l, int r) {
  if (l == r) {
    aint[0][v] = a[0][l];
  } else {
    int mid = (l + r) / 2;
    buildPar(2 * v, l, mid);
    buildPar(2 * v + 1, mid + 1, r);
    aint[0][v] = aint[0][2 * v] ^ aint[0][2 * v + 1];
  }
}

void buildImp(int v, int l, int r) {
  if (l == r) {
    aint[1][v] = a[1][l];
  } else {
    int mid = (l + r) / 2;
    buildImp(2 * v, l, mid);
    buildImp(2 * v + 1, mid + 1, r);
    aint[1][v] = aint[1][2 * v] ^ aint[1][2 * v + 1];
  }
}

void updatePar(int v, int l, int r, int pos, int val) {
  if (l == r) {
    aint[0][v] = val;
  } else {
    int mid = (l + r) / 2;
    if (pos <= mid) {
      updatePar(2 * v, l, mid, pos, val);
    } else {
      updatePar(2 * v + 1, mid + 1, r, pos, val);
    }
    aint[0][v] = aint[0][2 * v] ^ aint[0][2 * v + 1];
  }
}

void updateImp(int v, int l, int r, int pos, int val) {
  if (l == r) {
    aint[1][v] = val;
  } else {
    int mid = (l + r) / 2;
    if (pos <= mid) {
      updateImp(2 * v, l, mid, pos, val);
    } else {
      updateImp(2 * v + 1, mid + 1, r, pos, val);
    }
    aint[1][v] = aint[1][2 * v] ^ aint[1][2 * v + 1];
  }
}

int queryPar(int v, int l, int r, int p, int q) {
  if (p > q) {
    return 0;
  } else if (l == p && r == q) {
    return aint[0][v];
  } else {
    int mid = (l + r) / 2;
    return queryPar(2 * v, l, mid, p, std::min(mid, q)) ^ queryPar(2 * v + 1, mid + 1, r, std::max(p, mid + 1), q);
  }
}

int queryImp(int v, int l, int r, int p, int q) {
  if (p > q) {
    return 0;
  } else if (l == p && r == q) {
    return aint[1][v];
  } else {
    int mid = (l + r) / 2;
    return queryImp(2 * v, l, mid, p, std::min(mid, q)) ^ queryImp(2 * v + 1, mid + 1, r, std::max(p, mid + 1), q);
  }
}

int main() {
  int n, q;
  std::cin >> n >> q;
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i % 2][i / 2 + i % 2];
  }
  int len = (n + 1) / 2;
  buildImp(1, 1, len);
  buildPar(1, 1, n - len);
  while (q--) {
    int t;
    std::cin >> t;
    if (t == 1) {
      int pos, val;
      std::cin >> pos >> val;
      if (pos % 2 == 1) {
        updateImp(1, 1, len, (pos + 1) / 2, val);
      } else {
        updatePar(1, 1, n - len, pos / 2, val);
      }
    } else {
      int l, r;
      std::cin >> l >> r;
      if ((r - l + 1) % 2 == 0) {
        std::cout << "0\n";
      } else {
        if (l % 2 == 0) {
          std::cout << queryPar(1, 1, n - len, (l + 1) / 2, (r + 1) / 2) << "\n";
        } else {
          std::cout << queryImp(1, 1, len, (l + 1) / 2, (r + 1) / 2) << "\n";
        }
      }
    }
  }
  return 0;
}

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