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

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
// g++ <filename>.cpp -g -Wall -Wextra -DDEBUG -o <executable>
// copied from: https://codeforces.com/blog/entry/79024
// === Debug macro starts here ===
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream,ostream>::value, Ostream&>::type operator<<(Ostream& os, const Cont& v){
os<<"[";
for(auto& x:v){os<<x<<", ";}
return os<<"]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os, const pair<Ts...>& p){
return os<<"{"<<p.first<<", "<<p.second<<"}";
}
// === Debug macro ends here ===
// segment tree code from programmers handbook
int sum(vector<int> &tree, int n, int a, int b) {
a += n;
b += n;
int s = 0;
while (a <= b) {
if (a % 2 == 1) s ^= tree[a++];
if (b % 2 == 0) s ^= tree[b--];
a /= 2;
b /= 2;
}
return s;
}
// segment tree code from programmers handbook
void add(vector<int> &tree, int n, int k, int x) {
k += n;
tree[k] ^= x;
for (k /= 2; k >= 1; k /= 2) {
tree[k] = tree[2 * k] ^ tree[2 * k + 1];
}
}
signed main() {
int n, q;
cin >> n >> q;
vector<int> tree(4 * n, 0);
for (int i = 0; i < n; i++) {
int item;
cin >> item;
add(tree, n, i, item);
}
vector<int> sum_array(q);
for (int i = 0; i < q; i++) {
int a, b;
cin >> a >> b;
int s = sum(tree, n, a - 1, b - 1);
sum_array[i] = s;
}
for (int i = 0; i < q; i++) {
cout << sum_array[i] << "\n";
}
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