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

Code

#include <bits/stdc++.h>
using namespace std;
int segtree_create_rec(int input[], int segment_start, int segment_end, int *output, int index) {
if (segment_start == segment_end) {
output[index] = input[segment_start];
return output[index];
} else {
int mid = segment_start + (segment_end - segment_start) / 2;
int a = segtree_create_rec(input, segment_start, mid, output, 2*index+1);
int b = segtree_create_rec(input, mid+1, segment_end, output, 2*index+2);
output[index] = a ^ b;
return output[index];
}
}
int *segtree_create(int input[], int n) {
int x = (int) ceil(log2(n));
int max_size = 2 * (int) pow(2, x) - 1;
int *output = new int[max_size];
segtree_create_rec(input, 0, n-1, output, 0);
return output;
}
int segtree_xor_rec(int *segtree, int segment_start, int segment_end, int query_start, int query_end, int index) {
if (query_start <= segment_start && query_end >= segment_end)
return segtree[index];
if (segment_end < query_start || segment_start > query_end)
return 0;
int mid = segment_start + (segment_end - segment_start) / 2;
int a = segtree_xor_rec(segtree, segment_start, mid, query_start, query_end, 2*index+1);
int b = segtree_xor_rec(segtree, mid+1, segment_end, query_start, query_end, 2*index+2);
return a ^ b;
}
int segtree_xor(int *segtree, int n, int query_start, int query_end) {
// (query_start >= 0 && query_end <= n-1 && query_start <= query_end)
return segtree_xor_rec(segtree, 0, n-1, query_start, query_end, 0);
}
void segtree_update_rec(int *segtree, int index, int segment_start, int segment_end, int at, int new_value) {
int mid = segment_start + (segment_end - segment_start) / 2;
if (segment_start == segment_end && segment_start == at) {
segtree[index] = new_value;
} else if (mid >= at) {
segtree_update_rec(segtree, 2*index+1, segment_start, mid, at, new_value);
segtree[index] = min(segtree[2*index+1], segtree[2*index+2]);
} else {
segtree_update_rec(segtree, 2*index+2, mid+1, segment_end, at, new_value);
segtree[index] = min(segtree[2*index+1], segtree[2*index+2]);
}
}
void segtree_update(int *segtree, int n, int at, int new_value) {
segtree_update_rec(segtree, 0, 0, n-1, at, new_value);
}
int main() {
int n, q;
cin >> n >> q;
int *input = new int[n];
for (int i = 0; i < n; i++)
cin >> input[i];
int *segtree = segtree_create(input, n);
vector<int> output;
for (int i = 0; i < q; i++) {
int a, b;
cin >> a >> b;
int o = segtree_xor(segtree, n, a-1, b-1);
output.push_back(o);
}
for (long long o : output)
cout << o << endl;
return 0;
}

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