Task: | Xor sum |
Sender: | ZDHKLV |
Submission time: | 2024-09-23 16:54:03 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.60 s | details |
Code
#include <bits/stdc++.h>using namespace std;int segtree_create_rec(int input[], int segment_start, int segment_end, int *output, int index) {if (segment_start == segment_end) {output[index] = input[segment_start];return output[index];} else {int mid = segment_start + (segment_end - segment_start) / 2;int a = segtree_create_rec(input, segment_start, mid, output, 2*index+1);int b = segtree_create_rec(input, mid+1, segment_end, output, 2*index+2);output[index] = a ^ b;return output[index];}}int *segtree_create(int input[], int n) {int x = (int) ceil(log2(n));int max_size = 2 * (int) pow(2, x) - 1;int *output = new int[max_size];segtree_create_rec(input, 0, n-1, output, 0);return output;}int segtree_xor_rec(int *segtree, int segment_start, int segment_end, int query_start, int query_end, int index) {if (query_start <= segment_start && query_end >= segment_end)return segtree[index];if (segment_end < query_start || segment_start > query_end)return 0;int mid = segment_start + (segment_end - segment_start) / 2;int a = segtree_xor_rec(segtree, segment_start, mid, query_start, query_end, 2*index+1);int b = segtree_xor_rec(segtree, mid+1, segment_end, query_start, query_end, 2*index+2);return a ^ b;}int segtree_xor(int *segtree, int n, int query_start, int query_end) {// (query_start >= 0 && query_end <= n-1 && query_start <= query_end)return segtree_xor_rec(segtree, 0, n-1, query_start, query_end, 0);}void segtree_update_rec(int *segtree, int index, int segment_start, int segment_end, int at, int new_value) {int mid = segment_start + (segment_end - segment_start) / 2;if (segment_start == segment_end && segment_start == at) {segtree[index] = new_value;} else if (mid >= at) {segtree_update_rec(segtree, 2*index+1, segment_start, mid, at, new_value);segtree[index] = min(segtree[2*index+1], segtree[2*index+2]);} else {segtree_update_rec(segtree, 2*index+2, mid+1, segment_end, at, new_value);segtree[index] = min(segtree[2*index+1], segtree[2*index+2]);}}void segtree_update(int *segtree, int n, int at, int new_value) {segtree_update_rec(segtree, 0, 0, n-1, at, new_value);}int main() {int n, q;cin >> n >> q;int *input = new int[n];for (int i = 0; i < n; i++)cin >> input[i];int *segtree = segtree_create(input, n);vector<int> output;for (int i = 0; i < q; i++) {int a, b;cin >> a >> b;int o = segtree_xor(segtree, n, a-1, b-1);output.push_back(o);}for (long long o : output)cout << o << 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 |