Task: | Xor sum |
Sender: | eyong002 |
Submission time: | 2024-09-23 16:29:17 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.57 s | details |
Code
#include <iostream>#include <vector>#include <algorithm>#include <limits.h>using namespace std;int findXor(int a, int b, int t, vector<int>& tree){a += t;b += t;int m = 0;while (a <= b) {if (a%2 == 1) m = tree[a++] ^ m;if (b%2 == 0) m = tree[b--] ^ m;a /= 2; b /= 2;}return m;}int main() {int n, q;cin >> n >> q;vector<int> num(n);for (int i = 0; i < n; i++){cin >> num[i];}vector<vector<int>> queries(q, vector<int>(2));for (int i = 0; i < q; i++){for (int j = 0; j < 2; j++){cin >> queries[i][j];}}int t = 1;while (t < n) t *= 2;vector<int> segmentTree(2*t, 0);for (int i = 0; i < n; i++) {segmentTree[t+i] = num[i];}for (int i = t-1; i >= 1; i--){segmentTree[i] =segmentTree[2*i] ^ segmentTree[2*i+1];}for (int i = 0; i < q; i++){int a = queries[i][0];int b = queries[i][1];int sol = findXor(a-1, b-1, t, segmentTree);cout << sol << endl;}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 |