Task: | Xor sum |
Sender: | fabiank |
Submission time: | 2024-09-23 16:22:56 +0300 |
Language: | C++ (C++20) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.57 s | details |
Compiler report
input/code.cpp: In function 'std::vector<int> create_segment_tree(std::vector<int>&, int)': input/code.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare] 53 | for (int i = 0; i < values.size(); i++) | ~~^~~~~~~~~~~~~~~
Code
#include <bits/stdc++.h>using namespace std;vector<int> create_segment_tree(vector<int> &values, int n);void update_segment_tree(vector<int> &seg_tree, int i, int u, int n);int query_segment_tree(vector<int> &seg_tree, int a, int b, int n);int next_power_2(int x);void print_vector(vector<int> &x);// approach: SegmentTreesint main(){int n, q;cin >> n >> q;vector<int> values(n);for (int i = 0; i < n; i++){cin >> values[i];}int seg_tree_n = next_power_2(n);vector<int> seg_tree = create_segment_tree(values, seg_tree_n);for (int i = 0; i < q; i++){// int type;// cin >> type;// if (type == 1)// {// int k, u;// cin >> k >> u;// k--;// update_segment_tree(seg_tree, k, u, seg_tree_n);// }// else// {int a, b;cin >> a >> b;a--;b--;int query_result = query_segment_tree(seg_tree, a, b, seg_tree_n);cout << query_result << "\n";// }}}vector<int> create_segment_tree(vector<int> &values, int n){vector<int> seg_tree(2 * n, INT32_MAX);for (int i = 0; i < values.size(); i++){seg_tree[n + i] = values[i];}for (int i = n - 1; i > 0; i--){seg_tree[i] = seg_tree[2 * i] ^ seg_tree[2 * i + 1];}return seg_tree;}void update_segment_tree(vector<int> &seg_tree, int i, int u, int n){// print_vector(seg_tree);int k = i + n;// cout << "i: " << i << " - u: " << u << " - n: " << n << " - k: " << k << endl;seg_tree[k] = u;for (k /= 2; k >= 1; k /= 2){// cout << "k: " << k << endl;// print_vector(seg_tree);seg_tree[k] = min(seg_tree[2 * k], seg_tree[2 * k + 1]);}}int query_segment_tree(vector<int> &seg_tree, int a, int b, int n){a += n;b += n;int result = 0;while (a <= b){if (a % 2 == 1){result = result ^ seg_tree[a++];}if (b % 2 == 0){result = result ^ seg_tree[b--];}a /= 2;b /= 2;}return result;}int next_power_2(int x){// int exponent = ceil(log2(x));// return pow(2, exponent);int power_2 = 1;while (power_2 <= x){power_2 = power_2 << 1;}return power_2;}void print_vector(vector<int> &x){for (int v : x){cout << v << " ";}cout << "\n";}
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 |