oj.uz

Submission #983528

# Submission time Handle Problem Language Result Execution time Memory
983528 2024-05-15T15:43:19 Z Nomio XORanges (eJOI19_xoranges) C++17
100 / 100
 116 ms 11624 KB 
#include <bits/stdc++.h>
#define meta int tm = tl + (tr - tl) / 2, x = (i << 1) + 1, y = x + 1
using namespace std;
int st1[800001] {}, st2[800001] {};

void update1(int i, int tl, int tr, int l, int v) {
	if(tl == tr) {
		st1[i] = v;
		return;
	}
	meta;
	if(l <= tm) {
		update1(x, tl, tm, l, v);
	} else {
		update1(y, tm + 1, tr, l, v);
	}
	st1[i] = (st1[x] ^ st1[y]);
}

void update2(int i, int tl, int tr, int l, int v) {
	if(tl == tr) {
		st2[i] = v;
		return;
	}
	meta;
	if(l <= tm) {
		update2(x, tl, tm, l, v);
	} else {
		update2(y, tm + 1, tr, l, v);
	}
	st2[i] = (st2[x] ^ st2[y]);
}

int query1(int i, int tl, int tr, int l, int r) {
	if(l <= tl && tr <= r) {
		return st1[i];
	}
	meta;
	if(r <= tm) {
		return query1(x, tl, tm, l, r);
	} else if(l > tm) {
		return query1(y, tm + 1, tr, l, r);
	} else {
		return (query1(x, tl, tm, l, tm) ^ query1(y, tm + 1, tr, tm + 1, r));
	}
}

int query2(int i, int tl, int tr, int l, int r) {
	if(l <= tl && tr <= r) {
		return st2[i];
	}
	meta;
	if(r <= tm) {
		return query2(x, tl, tm, l, r);
	} else if(l > tm) {
		return query2(y, tm + 1, tr, l, r);
	} else {
		return (query2(x, tl, tm, l, tm) ^ query2(y, tm + 1, tr, tm + 1, r));
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, q;
	cin >> n >> q;
	for(int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if(i % 2 == 0) {
			update1(0, 0, n - 1, i, a);
		} else {
			update2(0, 0, n - 1, i, a);
		}
	}
	while(q--) {
		int t, l, r;
		cin >> t >> l >> r;
		if(t == 1) {
			l--;
			if(l % 2 == 0) {
				update1(0, 0, n - 1, l, r);	
			} else {
				update2(0, 0, n - 1, l, r);
			}
		} else {
			if((r - l + 1) % 2 == 0) {
				cout << 0 << '\n';
			} else {
				l--;
				r--;
				if(l % 2 == 0) {
					cout << query1(0, 0, n - 1, l, r) << '\n';
				} else {
					cout << query2(0, 0, n - 1, l, r) << '\n';
				}
			}
		}
	}
	return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2520 KB Output is correct
11 Correct 3 ms 2652 KB Output is correct
12 Correct 3 ms 2652 KB Output is correct
13 Correct 3 ms 2696 KB Output is correct
14 Correct 4 ms 2524 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 11624 KB Output is correct
2 Correct 115 ms 11600 KB Output is correct
3 Correct 111 ms 11488 KB Output is correct
4 Correct 103 ms 11088 KB Output is correct
5 Correct 103 ms 11308 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2396 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2396 KB Output is correct
10 Correct 1 ms 2520 KB Output is correct
11 Correct 3 ms 2652 KB Output is correct
12 Correct 3 ms 2652 KB Output is correct
13 Correct 3 ms 2696 KB Output is correct
14 Correct 4 ms 2524 KB Output is correct
15 Correct 116 ms 11624 KB Output is correct
16 Correct 115 ms 11600 KB Output is correct
17 Correct 111 ms 11488 KB Output is correct
18 Correct 103 ms 11088 KB Output is correct
19 Correct 103 ms 11308 KB Output is correct
20 Correct 105 ms 11344 KB Output is correct
21 Correct 114 ms 11192 KB Output is correct
22 Correct 113 ms 11268 KB Output is correct
23 Correct 104 ms 11220 KB Output is correct
24 Correct 105 ms 11096 KB Output is correct