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

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;
} else
return;
}
}
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