oj.uz

Submission #464031

# Submission time Handle Problem Language Result Execution time Memory
464031 2021-08-12T09:34:38 Z Alen777 XORanges (eJOI19_xoranges) C++14
55 / 100
 726 ms 2380 KB 
#include <iostream>
#include <string>
#include <iomanip>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

#define ll long long
#define ull unsigned ll
#define pb push_back
#define mpr make_pair
#define lb lower_bound
#define ld long double
#define ub upper_bound

const int N = 100002;

int a[N];
ll t[4 * N];

void build(int tl, int tr, int v) {
	if (tl == tr) {
		t[v] = a[tl];
	}
	else {
		int m = (tl + tr) / 2;
		build(tl, m, v * 2);
		build(m + 1, tr, v * 2 + 1);
		t[v] = t[v * 2] ^ t[v * 2 + 1];
	}
}

ll sum(int tl, int tr, int l, int r, int v) {
	if (l > r)
		return 0;
	if (l == tl && r == tr)
		return t[v];
	int m = (tl + tr) / 2;
	return sum(tl, m, l, min(r, m), v * 2)
		^ sum(m + 1, tr, max(l, m + 1), r, v * 2 + 1);
}

void update(int tl, int tr, int v, int pos, int new_val) {
	if (tl == tr) {
		t[v] = new_val;
	}
	else {
		int m = (tl + tr) / 2;
		if (pos <= m) {
			update(tl, m, v * 2, pos, new_val);
		}
		else {
			update(m + 1, tr, v * 2 + 1, pos, new_val);
		}
		t[v] = t[v * 2] ^ t[v * 2 + 1];
	}
}

void solve() {
	int n, q;
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	build(1, n, 1);
	for (int i = 1; i <= q; i++) {
		int c, l, r;
		cin >> c >> l >> r;
		if (c == 1) {
			update(1, n, 1, l, r);
		}
		else {
			if (r - l + 1 == 2) {
				cout << 0 << endl;
			}
			else if (r - l + 1 == 1) {
				cout << sum(1, n, l, r, 1) << endl;
			}
			else {
				ll ans = 0;
				if ((r - l + 1) % 2 == 0) {
					cout << 0 << endl;
				}
				else {
					for (int i = l; i <= r; i++) {
						if (i % 2 == l % 2) {
							ans ^= sum(1, n, i, i, 1);
						}
					}
					cout << ans << endl;
				}
			}
		}
	}
}

int main() {
    /*cout.setf(ios::fixed | ios::showpoint);
    cout.precision(6);*/
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

Subtask #1
12.0 / 12.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 #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.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
6 Correct 3 ms 332 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 6 ms 332 KB Output is correct
10 Correct 6 ms 332 KB Output is correct
11 Correct 144 ms 588 KB Output is correct
12 Correct 151 ms 588 KB Output is correct
13 Correct 715 ms 696 KB Output is correct
14 Correct 726 ms 588 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 14 ms 2380 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 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
6 Correct 3 ms 332 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 4 ms 332 KB Output is correct
9 Correct 6 ms 332 KB Output is correct
10 Correct 6 ms 332 KB Output is correct
11 Correct 144 ms 588 KB Output is correct
12 Correct 151 ms 588 KB Output is correct
13 Correct 715 ms 696 KB Output is correct
14 Correct 726 ms 588 KB Output is correct
15 Runtime error 14 ms 2380 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -