제출 #943779

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
943779		stefanneagu	XORanges (eJOI19_xoranges)	C++17	55 / 100	10 ms	860 KiB

xoranges

#include <bits/stdc++.h>

using namespace std;

const int nmax = 5001;

struct AINT {
  int aint[nmax * 4];

  void init() {
    memset(aint, 0, sizeof(aint));
  }

  void update(int nod, int st, int dr, int poz, int val) {
    if(st == dr) {
      aint[nod] = val;
      return;
    }
    int mid = (st + dr) / 2;
    if(poz <= mid) {
      update(nod * 2, st, mid, poz, val);
    } else {
      update(nod * 2 + 1, mid + 1, dr, poz, val);
    }
    aint[nod] = (aint[nod * 2] ^ aint[nod * 2 + 1]);
  }

  int query(int nod, int st, int dr, int l, int r) {
    if(l <= st && dr <= r) {
      return aint[nod];
    }
    int mid = (st + dr) / 2, a1 = 0, a2 = 0;
    if(l <= mid) {
      a1 = query(nod * 2, st, mid, l, min(r, mid));
    }
    if(r > mid) {
      a2 = query(nod * 2 + 1, mid + 1, dr, max(l, mid + 1), r);
    }
    return (a1 ^ a2);
  }
};

int main() {
  AINT s1, s2;
  /*
  for(int i = 1; i <= 5; i ++) {
    s1.update(1, 1, 5, i, i);
  }
  for(int i = 1; i <= 5; i ++) {
    cout << s1.query(1, 1, 5, i, i) << ' ';
  }
  cout << '\n';
  */
  s1.init();
  s2.init();
  int n, q;
  cin >> n >> q;
  int ok = n % 2;
  for(int i = 1; i <= n; i ++) {
    int a;
    cin >> a;
    if(i % 2 == 0) {
      s1.update(1, 1, n / 2, i / 2, a);
      // cout << s1.query(1, 1, n / 2 + 1, i / 2, i / 2) << " ";
    } else {
      s2.update(1, 1, n / 2 + ok, i / 2 + 1, a);
      // cout << s2.query(1, 1, n / 2 + 1, i / 2 + 1, i / 2 + 1) << " ";
    }
  }
  // cout << '\n';
  // cout << "sirul: ";
  /*
  for(int ii = 1; ii <= n; ii ++) {
    if(ii % 2 == 0) {
      cout << s1.query(1, 1, n / 2, ii / 2, ii / 2) << " ";
    } else {
      cout << s2.query(1, 1, n / 2 + ok, ii / 2 + 1, ii / 2 + 1) << " ";
    }
  }
  cout << '\n';
  */
  for(int i = 1; i <= q; i ++) {
    int t, a, b;
    cin >> t >> a >> b;
    if(t == 1) {
      if(a % 2 == 0) {
        s1.update(1, 1, n / 2, a / 2, b);
      } else {
        s2.update(1, 1, n / 2 + ok, a / 2 + 1, b);
      }
    } else {
      if((b - a + 1) % 2 == 0) {
        cout << "0\n";
      } else if(a % 2 == 0) {
        cout << s1.query(1, 1, n / 2, a / 2, b / 2) << '\n';
      } else {
        cout << s2.query(1, 1, n / 2 + ok, a / 2 + 1, b / 2 + 1) << '\n';
      }
    }
  }
  return 0;
}

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