Task: | Xor sum |
Sender: | aarol |
Submission time: | 2024-09-23 16:26:05 +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 <bits/stdc++.h>using namespace std;int n;int tree_min(vector<int> &tree, int a, int b) {a += n;b += n;int m = 0;while (a <= b) {if ((a % 2) == 1) {m ^= tree[a];a++;}if ((b % 2) == 0) {m ^= tree[b];b--;}a /= 2;b /= 2;}return m;}void update(vector<int> &tree, int i, int v) {i += n;tree[i] = v;int newMin;while (i > 1) {i /= 2;newMin = tree[2 * i] ^ tree[2 * i + 1];if (tree[i] != newMin) {tree[i] = newMin;} elsereturn;}}int main() {//ios::sync_with_stdio(false);//cin.tie(0);int q;cin >> n >> q;auto values = vector<int>(n);for (int i = 0; i < n; i++) {cin >> values[i];}int tree_size = 2 * n;auto tree = vector<int>(tree_size, 1e9+5);for (int i = n; i < tree_size; i++) {tree[i] = values[i - n];}for (int i = n - 1; i > 0; i--) {tree[i] = tree[2 * i] ^ tree[2 * i + 1];}for (int i = 0; i < q; i++) {int a, b;cin >> a >> b;// query [a,b]cout << tree_min(tree, 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 |