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

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define SEG_OP(a,b) a ^ b
const int N = 1<<19;
struct Seg {
int S[N*2];
Seg(int x = 0) {
for (int i = N; i < N*2; ++i) S[i] = x;
for (int i = N-1; i >= 1; --i) S[i] = SEG_OP(S[i*2], S[i*2+1]);
}
void set(int i, int x) {
i |= N;
S[i] = x;
for (i /= 2; i >= 1; i /= 2) {
S[i] = SEG_OP(S[i*2], S[i*2+1]);
}
}
ll get(int a, int b, ll s = 0) {
a |= N; b |= N;
while (a <= b) {
if (a % 2 == 1) s = SEG_OP(s, ll(S[a++]));
if (b % 2 == 0) s = SEG_OP(s, ll(S[b--]));
a /= 2; b /= 2;
}
return s;
}
};
int n, q;
Seg S;
int main() {
cin >> n >> q;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
S.set(i+1,x);
}
for (int i = 0; i < q; ++i) {
int a, b;
cin >> a >> b;
cout << S.get(a,b) << '\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