oj.uz

Submission #603709

# Submission time Handle Problem Language Result Execution time Memory
603709 2022-07-24T10:05:18 Z Lextyle XORanges (eJOI19_xoranges) C++17
100 / 100
 124 ms 13292 KB 
#include <bits/stdc++.h>
#pragma warning(disable : 4996)
#pragma warning(disable : 6031)
#define USACO freopen("clumsy.in", "r", stdin); freopen("clumsy.out", "w+", stdout);    
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
pair<int, pair<int, int>> segtree[600000];
int a[300000];

void build(int node, int l, int r) {
	if (r - l + 1 == 1) {
		segtree[node].first = a[l];
		segtree[node].second.first = a[l];
		return;
	}
	int mid = l + (r - l + 1) / 2;
	build(node * 2, l, mid - 1);
	build(node * 2 + 1, mid, r);
	if (r - l + 1 == 2) {
		segtree[node].first = segtree[node * 2].first ^ segtree[node * 2 + 1].first;
		segtree[node].second.first = segtree[node * 2].first;
		segtree[node].second.second = segtree[node * 2 + 1].first;
		return;
	}
	segtree[node].first = segtree[node * 2].first ^ segtree[node * 2 + 1].first;
	segtree[node].second.first = segtree[node * 2].second.first ^ segtree[node * 2 + 1].second.first;
	segtree[node].second.second = segtree[node * 2].second.second ^ segtree[node * 2 + 1].second.second;
}

void change(int node, int l, int r, int i, int x) {
	if (r - l + 1 == 1) {
		segtree[node].first = x;
		segtree[node].second.first = x;
		return;
	}
	int mid = l + (r - l + 1) / 2;
	if (i < mid) change(node * 2, l, mid - 1, i, x);
	else  change(node * 2 + 1, mid, r, i, x);
	if (r - l + 1 == 2) {
		segtree[node].first = segtree[node * 2].first ^ segtree[node * 2 + 1].first;
		segtree[node].second.first = segtree[node * 2].first;
		segtree[node].second.second = segtree[node * 2 + 1].first;
		return;
	}
	segtree[node].first = segtree[node * 2].first ^ segtree[node * 2 + 1].first;
	segtree[node].second.first = segtree[node * 2].second.first ^ segtree[node * 2 + 1].second.first;
	segtree[node].second.second = segtree[node * 2].second.second ^ segtree[node * 2 + 1].second.second;
}

int getxor(int node, int l, int r, int lq, int rq) {
	if (l >= lq && r <= rq)
		if ((l - lq + 1) % 2) return segtree[node].second.first;
		else return segtree[node].second.second;
	else if (r < lq || l > rq) return 0;
	else {
		int mid = l + (r - l + 1) / 2;
		return getxor(node * 2, l, mid - 1, lq, rq) ^ getxor(node * 2 + 1, mid, r, lq, rq);
	}
}

int main() {
	//USACO;
	fastIO;
	int n, q;
	cin >> n >> q;
	for (int i = 0; i < n; i++) cin >> a[i];
	int newn = 1;
	while (newn < n) newn <<= 1;
	n = newn;
	build(1, 0, n - 1);
	while (q--) {
		int i;
		cin >> i;
		if (i == 1) {
			int j, x;
			cin >> j >> x; j--;
			change(1, 0, n - 1, j, x);
		}
		else {
			int l, r;
			cin >> l >> r; l--; r--;
			if ((r - l + 1) % 2 == 0) cout << "0\n";
			else cout << getxor(1, 0, n - 1, l, r) << "\n";
		}
	}
}

Compilation message

xoranges.cpp:2: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    2 | #pragma warning(disable : 4996)
      | 
xoranges.cpp:3: warning: ignoring '#pragma warning ' [-Wunknown-pragmas]
    3 | #pragma warning(disable : 6031)
      |

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 4 ms 572 KB Output is correct
13 Correct 4 ms 596 KB Output is correct
14 Correct 3 ms 596 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 13268 KB Output is correct
2 Correct 124 ms 13292 KB Output is correct
3 Correct 116 ms 13240 KB Output is correct
4 Correct 103 ms 12944 KB Output is correct
5 Correct 103 ms 12848 KB Output is correct

Subtask #5
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 4 ms 572 KB Output is correct
13 Correct 4 ms 596 KB Output is correct
14 Correct 3 ms 596 KB Output is correct
15 Correct 121 ms 13268 KB Output is correct
16 Correct 124 ms 13292 KB Output is correct
17 Correct 116 ms 13240 KB Output is correct
18 Correct 103 ms 12944 KB Output is correct
19 Correct 103 ms 12848 KB Output is correct
20 Correct 123 ms 12932 KB Output is correct
21 Correct 118 ms 13080 KB Output is correct
22 Correct 120 ms 12980 KB Output is correct
23 Correct 105 ms 12868 KB Output is correct
24 Correct 110 ms 12876 KB Output is correct