Task: | Xor sum |
Sender: | snude |
Submission time: | 2024-09-23 16:42:15 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.56 s | details |
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 endfor (int i = 0; i < n; i++) {tree[size + i] = input[i];}// start from the end, from the second last element -> -2for (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 parametersint n, q;cin >> n >> q;// Read values from one linevector<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 queryingfirst--;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 |