oj.uz

Submission #466161

# Submission time Handle Problem Language Result Execution time Memory
466161 2021-08-18T08:50:02 Z MKutayBozkurt XORanges (eJOI19_xoranges) C++14
100 / 100
 116 ms 3928 KB 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class fenwickTree {
  public:
    vector<int> table;
    int n;
    fenwickTree(int N) {
      n = N + 1;
      table.resize(n);
    }
    int query(int i) {
      int v{};
			i++;
      while (i > 0) {
        v ^= table[i];
        i -= i & (-i);
      }
      return v;
    }
    int range_query(int l, int r) {
      return query(r) ^ query(l - 1);
    }
		void update(int i, int delta) {
			int prev = range_query(i, i);
			i++;
      while (i < n) {
				table[i] ^= prev;
        table[i] ^= delta;
        i += i & (-i);
      }
    }
};

int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int n, q; cin >> n >> q;
  vector<int> a(n); for (int &x : a) cin >> x;
	fenwickTree ft1(n), ft0(n);

	for (int i = 0; i < n; i++) {
		if (i % 2) {
			ft1.update(i, a[i]);
		} else {
			ft0.update(i, a[i]);
		}
	}

	while (q--) {
		int op; cin >> op;
		if (op == 1) {
			int i, v; cin >> i >> v, i--;
			if (i % 2) {
				ft1.update(i, v);
			} else {
				ft0.update(i, v);
			}
		} else {
			int l, r; cin >> l >> r, l--, r--;
			if ((r - l + 1) % 2 == 0) {
				cout << "0\n";
			} else if (l % 2) {
				cout << ft1.range_query(l, r) << '\n';
			} else {
				cout << ft0.range_query(l, r) << '\n';
			}
		}
	}
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 3928 KB Output is correct
2 Correct 114 ms 3912 KB Output is correct
3 Correct 112 ms 3784 KB Output is correct
4 Correct 104 ms 3776 KB Output is correct
5 Correct 104 ms 3860 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 4 ms 332 KB Output is correct
13 Correct 3 ms 332 KB Output is correct
14 Correct 3 ms 332 KB Output is correct
15 Correct 114 ms 3928 KB Output is correct
16 Correct 114 ms 3912 KB Output is correct
17 Correct 112 ms 3784 KB Output is correct
18 Correct 104 ms 3776 KB Output is correct
19 Correct 104 ms 3860 KB Output is correct
20 Correct 110 ms 3152 KB Output is correct
21 Correct 116 ms 3240 KB Output is correct
22 Correct 114 ms 3248 KB Output is correct
23 Correct 103 ms 3792 KB Output is correct
24 Correct 113 ms 3680 KB Output is correct