oj.uz

Submission #929232

# Submission time Handle Problem Language Result Execution time Memory
929232 2024-02-18T03:56:45 Z erkhem XORanges (eJOI19_xoranges) C++14
12 / 100
 1000 ms 8284 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'
#define ff first
#define ss second
#define rev reverse
#define pb push_back
#define all(a) a.begin(), a.end()
#define maxx(a, b) a = max(a, b);
#define minn(a, b) a = min(a, b);
#define fastio cin.tie(0)->sync_with_stdio(0)
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<bool> vb;
typedef vector<string> vs;

const int mod = 1e9 + 7;
const int inf = 1e18;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {-1, 0, 1, 0};

vi a;
vi sum;

void build(int id, int L, int R) {
	if (L == R) {
		sum[id] = a[L];
		return;
	}
	int M = (L + R) / 2, x = 2 * id + 1, y = 2 * id + 2;
	build(x, L, M);
	build(y, M + 1, R);
	sum[id] = sum[x] ^ sum[y];
}

void update(int id, int L, int R, int i, int k) {
	if (L == R) {
		sum[id] = k;
		return;
	}
	int M = (L + R) / 2, x = 2 * id + 1, y = x + 1;
	if (i <= M) {
		update(x, L, M, i, k);
	} else {
		update(y, M + 1, R, i, k);
	}
	sum[id] = sum[x] ^ sum[y];
}

long long query(int id, int L, int R, int l, int r) {
	if (L == l && r == R) {
		return sum[id];
	}
	int M = (L + R) / 2, x = 2 * id + 1, y = x + 1;
	if (r <= M)
		return query(x, L, M, l, r);
	if (M + 1 <= l)
		return query(y, M + 1, R, l, r);
	return query(x, L, M, l, M) ^ query(y, M + 1, R, M + 1, r);
}

int32_t main() {
	fastio;
	int n, q;
	cin >> n >> q;
	a.resize(n);
	sum.resize(4 * n + 10);
	rep(i, n) {
		cin >> a[i];
	}
	build(0, 0, n - 1);
	while (q--) {
		int c, l, r;
		cin >> c >> l >> r;
		if (c == 1) {
			update(0, 0, n - 1, l - 1, r);
		}
		else {
			int ans = 0;
			for (int i = l; i <= r; i++) {
				for (int j = i; j <= r; j++) {
					ans ^= query(0, 0, n - 1, i - 1, j - 1);
				}
			}
			cout << ans << endl;
		}
	}
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 16 ms 348 KB Output is correct
5 Correct 16 ms 604 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 803 ms 456 KB Output is correct
2 Correct 715 ms 472 KB Output is correct
3 Correct 892 ms 464 KB Output is correct
4 Execution timed out 1043 ms 348 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 16 ms 348 KB Output is correct
5 Correct 16 ms 604 KB Output is correct
6 Correct 803 ms 456 KB Output is correct
7 Correct 715 ms 472 KB Output is correct
8 Correct 892 ms 464 KB Output is correct
9 Execution timed out 1043 ms 348 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1050 ms 8284 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 16 ms 348 KB Output is correct
5 Correct 16 ms 604 KB Output is correct
6 Correct 803 ms 456 KB Output is correct
7 Correct 715 ms 472 KB Output is correct
8 Correct 892 ms 464 KB Output is correct
9 Execution timed out 1043 ms 348 KB Time limit exceeded
10 Halted 0 ms 0 KB -