oj.uz

Submission #943779

# Submission time Handle Problem Language Result Execution time Memory
943779 2024-03-11T21:54:09 Z stefanneagu XORanges (eJOI19_xoranges) C++17
55 / 100
 10 ms 860 KB 
#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.0 / 12.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 #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.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
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 8 ms 604 KB Output is correct
12 Correct 8 ms 704 KB Output is correct
13 Correct 10 ms 604 KB Output is correct
14 Correct 10 ms 600 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.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
6 Correct 2 ms 348 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 8 ms 604 KB Output is correct
12 Correct 8 ms 704 KB Output is correct
13 Correct 10 ms 604 KB Output is correct
14 Correct 10 ms 600 KB Output is correct
15 Runtime error 1 ms 860 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -