oj.uz

Submission #254493

# Submission time Handle Problem Language Result Execution time Memory
254493 2020-07-30T06:35:28 Z lani1akea XORanges (eJOI19_xoranges) C++17
0 / 100
 136 ms 6732 KB 
#include <bits/stdc++.h>

#define F first
#define S second
#define ll long long
#define pb push_back
#define endl '\n'

using namespace std;

const int MOD = 1e9 + 7;
const int N = 2 * 1e5 + 1;

int n, q, a[N], t1[4*N], t2[4*N], ty;
void build(int v, int tl, int tr) {
  if (tl == tr) {
    if (tl % 2 ) t1[v] = a[tl];
    else t2[v] = a[tl];
    return;
  }
  int tm = (tl + tr) / 2;
  build(v*2, tl, tm); build(v*2+1, tm+1, tr);
  t1[v] = t1[v*2] ^ t1[v*2+1];
  t2[v] = t2[v*2] ^ t2[v*2+1];
}

int get(int v, int tl, int tr, int l, int r, int type) {
  if (l > r) return 0;
  if (tl >= l and tr <= r) {
    if (type == 1) return t1[v];
    else return t2[v];
  }
  int tm = (tl + tr) / 2;
  return get(v*2, tl, tm, l, min(tm, r), type) ^ get(v*2+1, tm+1, tr, max(tm+1, tl), tr, type);
}

void update(int v, int tl, int tr, int pos, int new_value) {
  if (tl == tr) {
    if (pos % 2) t1[v] = new_value;
    else t2[v] = new_value;
    return;
  }
  int tm = (tl + tr) / 2;
  if (pos <= tm) update(v*2, tl, tm, pos, new_value);
  else update(v*2+1, tm+1, tr, pos, new_value);
  t1[v] = t1[v*2] ^ t1[v*2+1];
  t2[v] = t2[v*2] ^ t2[v*2+1];
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> q;

  for (int i = 0; i < n; ++i)
    cin >> a[i];

  build(1, 0, n - 1);

  while (q--) {
    int ty, i, j;
    cin >> ty >> i >> j;
    if (ty == 1) update(1, 0, n - 1, --i, j);
    else if(i % 2 != j % 2) cout << "0\n";
    else if(i % 2) cout << get(1, 0, n-1, i-1, j-1, 2) << endl;
    else cout << get(1, 0, n-1, i-1, j-1, 1) << endl;
  }
}

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 136 ms 6732 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -