oj.uz

Submission #282281

# Submission time Handle Problem Language Result Execution time Memory
282281 2020-08-24T08:39:24 Z lani1akea XORanges (eJOI19_xoranges) C++17
100 / 100
 176 ms 11384 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 mxN = 2e5;

int a[mxN], t1[4 * mxN], t2[4 * mxN];

void build(int x, int l, int r) {
  if (l == r) {
    (l % 2 ? t1[x] : t2[x]) = a[l];
    return;
  }
  int m = (l + r) / 2;
  build(x * 2, l, m);
  build(x * 2 + 1, m + 1, r);
  t1[x] = t1[x * 2] ^ t1[x * 2 + 1];  
  t2[x] = t2[x * 2] ^ t2[x * 2 + 1];
}

void update(int x, int l, int r, int i, int val) {
	if (l == r) {
		if (i % 2) t1[x] = val;
		else t2[x] = val;
		return;
	}
	int m = (l + r) / 2;
	if (i > m) update(x * 2 + 1, m + 1, r, i, val);
	else update(x * 2, l, m, i, val);
	t1[x] = t1[x * 2] ^ t1[x * 2 + 1];
	t2[x] = t2[x * 2] ^ t2[x * 2 + 1];
}

int get(int x, int lx, int rx, int l, int r, int t) {
  if (lx > r or rx < l) return 0;
  if (lx >= l and rx <= r) {
   	if (t & 1) return t1[x];
   	else return t2[x];
  }
  int m = (lx + rx) / 2;
  return get(x*2, lx, m, l, r, t) ^ get(x * 2 + 1, m + 1, rx, l, r, t);
}             

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  int n, q;
  cin >> n >> q;
  for (int i = 0; i < n; ++i)
    cin >> a[i];

  build(1, 0, n - 1);
  while(q--) {
    int t, a, b;
    cin >> t >> a >> b;
    if (t&1) {
      update(1, 0, n - 1, a - 1, b);
    } else {
      if (a % 2 != b % 2) {
        cout << "0\n";
      } else {
        cout << get(1, 0, n - 1, a - 1, b - 1, (a - 1) % 2) << endl;
      }
    }
  }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 11384 KB Output is correct
2 Correct 167 ms 11268 KB Output is correct
3 Correct 159 ms 11384 KB Output is correct
4 Correct 130 ms 11004 KB Output is correct
5 Correct 130 ms 11000 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 3 ms 640 KB Output is correct
12 Correct 3 ms 640 KB Output is correct
13 Correct 3 ms 640 KB Output is correct
14 Correct 3 ms 640 KB Output is correct
15 Correct 162 ms 11384 KB Output is correct
16 Correct 167 ms 11268 KB Output is correct
17 Correct 159 ms 11384 KB Output is correct
18 Correct 130 ms 11004 KB Output is correct
19 Correct 130 ms 11000 KB Output is correct
20 Correct 155 ms 11000 KB Output is correct
21 Correct 176 ms 11000 KB Output is correct
22 Correct 149 ms 11000 KB Output is correct
23 Correct 131 ms 10872 KB Output is correct
24 Correct 131 ms 10872 KB Output is correct