CSES - Aalto Competitive Programming 2024 - wk4 - Mon - Results
Submission details
Task:Xor sum
Sender:arnxxau
Submission time:2024-09-23 16:24:06 +0300
Language:C++ (C++11)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.61 sdetails

Code

#include <climits>
#include <iostream>
#include <vector>
// Clase para manejar sumas de segmentos
class SumSegmentTree {
private:
std::vector<int> tree;
std::vector<int> data;
int n;
void build(int node, int start, int end) {
if (start == end) {
tree[node] = data[start];
} else {
int mid = (start + end) / 2;
build(2 * node + 1, start, mid);
build(2 * node + 2, mid + 1, end);
tree[node] = tree[2 * node + 1] ^ tree[2 * node + 2];
}
}
int query(int node, int start, int end, int l, int r) {
if (r < start || l > end) {
return 0;
}
if (l <= start && end <= r) {
return tree[node];
}
int mid = (start + end) / 2;
return query(2 * node + 1, start, mid, l, r) ^ query(2 * node + 2, mid + 1, end, l, r);
}
void update(int node, int start, int end, int idx, int value) {
if (start == end) {
data[idx] = value;
tree[node] = value;
} else {
int mid = (start + end) / 2;
if (start <= idx && idx <= mid) {
update(2 * node + 1, start, mid, idx, value);
} else {
update(2 * node + 2, mid + 1, end, idx, value);
}
tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
}
}
public:
SumSegmentTree(const std::vector<int>& initial_data) : data(initial_data) {
n = initial_data.size();
tree.resize(4 * n);
build(0, 0, n - 1);
}
int sum(int l, int r) {
return query(0, 0, n - 1, l, r);
}
void update(int idx, int value) {
update(0, 0, n - 1, idx, value);
}
};
using namespace std;
int main() {
int n, q;
cin >> n >> q;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
SumSegmentTree t(arr);
for (int i = 0; i < q; i++) {
int a, b;
cin >> a >> b;
cout << t.sum(a - 1, b - 1) << endl;
}
}

Test details

Test 1

Verdict: ACCEPTED

input
8 36
7 6 4 6 2 9 4 8
1 1
1 2
1 3
...

correct output
7
1
5
3
1
...

user output
7
1
5
3
1
...

Test 2

Verdict: ACCEPTED

input
200000 200000
921726510 307633388 992247073 ...

correct output
834756431
130379787
403037296
308618218
784778243
...

user output
834756431
130379787
403037296
308618218
784778243
...
Truncated