oj.uz

Submission #773966

# Submission time Handle Problem Language Result Execution time Memory
773966 2023-07-05T10:06:18 Z Tkm_algo XORanges (eJOI19_xoranges) C++17
0 / 100
 140 ms 11932 KB 
#include "bits/stdc++.h"

using namespace std;
using ll = long long;

struct node {
	int x;
};
 
struct segtree {
 
	vector<node> tree;
	int size;
	node def = {0};
	
	node combine(node a, node b) {
		return {a.x ^ b.x};
	}
 
	void init(int n) {
		size = 1;
		while (size < n) size *= 2;
		tree.assign(2 * size - 1, def);
	}
	
	void set(int i, node v, int x, int lx, int rx) {
		if (rx - lx == 1) {
			tree[x] = v;
			return;
		}
		int m = (lx + rx) / 2;
		if (i < m) {
			set(i, v, 2 * x + 1, lx, m);
		} else {
			set(i, v, 2 * x + 2, m, rx);
		}
		tree[x] = combine(tree[2 * x + 1], tree[2 * x + 2]);
	}
	
	void set(int i, node v) {
		set(i, v, 0, 0, size);
	}
	
	node res(int l, int r, int x, int lx, int rx) {
		if (l >= rx || lx >= r) {
			return def;
		}
		if (lx >= l && rx <= r) {
			return tree[x];
		}
		int m = (lx + rx) / 2;
		node s1 = res(l, r, 2 * x + 1, lx, m);
		node s2 = res(l, r, 2 * x + 2, m, rx);
		return combine(s1, s2);
	}
	
	node res(int l, int r) {
		return res(l, r, 0, 0, size);
	}
};

void solve() {
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	segtree st0, st1;
	st0.init(n);
	st1.init(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		if (a[i] & 1) {
			st1.set(i, {a[i]});
		} else {
			st0.set(i, {a[i]});
		}
	}
	while (q--) {
		int c;
		cin >> c;
		if (c == 1) {
			int i, j;
			cin >> i >> j;
			if (i & 1) {
				st1.set(i - 1, {j});
			} else {
				st0.set(i - 1, {j});
			}
		} else {
			int l, r;
			cin >> l >> r;
			if (l & 2 != r & 2) {
				cout << "0\n";
			} else {
				if (l & 1) {
					cout << st1.res(l - 1, r).x << '\n';
				} else  {
					cout << st0.res(l - 1, r).x << '\n';
				}
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int test = 1;
	// cin >> test;
	
	while (test--) {
		solve();
	}
}

Compilation message

xoranges.cpp: In function 'void solve()':
xoranges.cpp:91:14: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   91 |    if (l & 2 != r & 2) {
      |            ~~^~~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 140 ms 11932 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 212 KB Output isn't correct
2 Halted 0 ms 0 KB -