Task: | Xor sum |
Sender: | MallocManfred |
Submission time: | 2024-09-23 16:25:16 +0300 |
Language: | C++ (C++20) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.29 s | details |
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)#endiftemplate<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 handbookint 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 handbookvoid 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 |