#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q;
vector<int> numbers;
vector<vector<int> > bits;
vector<vector<int> > prefix_sum;
void update() {
int pos, val;
cin >> pos >> val;
numbers[pos] = val;
for(int i = 0; i < 30; ++i) {
if(numbers[pos] & (1 << i)) {
bits[pos][i] = true;
} else {
bits[pos][i] = false;
}
}
prefix_sum[1] = bits[1];
for(int i = 2; i <= n; ++i) {
for(int j = 0; j < 30; ++j) {
prefix_sum[i][j] = prefix_sum[i - 2][j];
if(bits[i][j]) {
prefix_sum[i][j] = (1 - prefix_sum[i][j]);
}
}
}
}
void query() {
int l, r;
cin >> l >> r;
if((r - l + 1) % 2 == 0) {
cout << "0\n";
return;
}
vector<int> ans(30, 0);
ans = prefix_sum[r];
for(int i = 0; i < 30; ++i) {
if(bits[l][i]) {
ans[i] = (1 - ans[i]);
}
if(prefix_sum[l][i]) {
ans[i] = (1 - ans[i]);
}
}
int result = 0;
for(int i = 0; i < 30; ++i) {
result += ans[i] * (1 << i);
}
cout << result << "\n";
}
void solve() {
cin >> n >> q;
numbers.assign(1 + n, 0);
bits.assign(1 + n, vector<int> (30, 0));
prefix_sum.assign(1 + n, vector<int> (30, 0));
for(int i = 1; i <= n; ++i) {
cin >> numbers[i];
for(int j = 0; j < 30; ++j) {
if(numbers[i] & (1 << j)) {
bits[i][j] = 1;
}
if(i == 1) continue;
prefix_sum[i][j] = prefix_sum[i - 2][j];
if(bits[i][j]) {
prefix_sum[i][j] = (1 - prefix_sum[i][j]);
}
}
if(i == 1) prefix_sum[i] = bits[i];
}
while(q--) {
int type = 0;
cin >> type;
if(type == 1) update();
else query();
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
1 ms |
460 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
1 ms |
460 KB |
Output is correct |
5 |
Correct |
1 ms |
448 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
448 KB |
Output is correct |
11 |
Execution timed out |
1082 ms |
1916 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
307 ms |
65536 KB |
Output is correct |
2 |
Correct |
306 ms |
65536 KB |
Output is correct |
3 |
Correct |
318 ms |
65536 KB |
Output is correct |
4 |
Correct |
263 ms |
65536 KB |
Output is correct |
5 |
Correct |
271 ms |
65536 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
460 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
460 KB |
Output is correct |
9 |
Correct |
1 ms |
460 KB |
Output is correct |
10 |
Correct |
1 ms |
448 KB |
Output is correct |
11 |
Execution timed out |
1082 ms |
1916 KB |
Time limit exceeded |
12 |
Halted |
0 ms |
0 KB |
- |