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

Code

#include <climits>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
int get_min(int a, int b, vector<int> &tree, int n) {
a += n; b += n;
int s = 0;
while (a <= b) {
if (a%2 == 1) s = tree[a++] ^ s;
if (b%2 == 0) s = tree[b--] ^ s;
a /= 2; b /= 2;
}
return s;
}
int bit_ceil(int n) {
int res = 1;
while (res < n) res <<= 1;
return res;
}
vector<int> create_segment_tree(int n, vector<int> &input, int size) {
vector<int> tree(2 * size, INT_MAX);
// Add input to the end
for (int i = 0; i < n; i++) {
tree[size + i] = input[i];
}
// start from the end, from the second last element -> -2
for (int i = size * 2 - 2; i > 0; i -= 2) {
tree[i/2] = tree[i]^tree[i + 1];
}
return tree;
}
int main(int argc, char *argv[])
{
// Read the input parameters
int n, q;
cin >> n >> q;
// Read values from one line
vector<int> input_line(n);
for (int i = 0; i < n; i++) {
cin >> input_line[i];
}
int size = bit_ceil(n);
vector<int> segment_tree = create_segment_tree(n, input_line, size);
for (int i = 0; i < q; i++) {
int first, second;
cin >> first >> second;
// I use zero based indexing, second must be reduced only when querying
first--;
second--;
cout << get_min(first, second, segment_tree, size) << "\n";
}
// for (int i = 0; i < size * 2; i++) {
// cout << segment_tree[i] << " ";
// }
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