oj.uz

Submission #1071587

# Submission time Handle Problem Language Result Execution time Memory
1071587 2024-08-23T09:06:29 Z DariusH XORanges (eJOI19_xoranges) C++14
100 / 100
 368 ms 7884 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 6 ms 604 KB Output is correct
12 Correct 8 ms 600 KB Output is correct
13 Correct 9 ms 604 KB Output is correct
14 Correct 9 ms 604 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 355 ms 3168 KB Output is correct
2 Correct 368 ms 7800 KB Output is correct
3 Correct 360 ms 7884 KB Output is correct
4 Correct 348 ms 7508 KB Output is correct
5 Correct 348 ms 7504 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 6 ms 604 KB Output is correct
12 Correct 8 ms 600 KB Output is correct
13 Correct 9 ms 604 KB Output is correct
14 Correct 9 ms 604 KB Output is correct
15 Correct 355 ms 3168 KB Output is correct
16 Correct 368 ms 7800 KB Output is correct
17 Correct 360 ms 7884 KB Output is correct
18 Correct 348 ms 7508 KB Output is correct
19 Correct 348 ms 7504 KB Output is correct
20 Correct 253 ms 7508 KB Output is correct
21 Correct 268 ms 7504 KB Output is correct
22 Correct 267 ms 7508 KB Output is correct
23 Correct 346 ms 7556 KB Output is correct
24 Correct 344 ms 7440 KB Output is correct