Submission details
Task:Xor sum
Sender:aalto26dm_035
Submission time:2026-09-21 16:27:50 +0300
Language:C++ (C++20)
Status:READY
Result:ACCEPTED
Test results
testverdicttime
#1ACCEPTED0.00 sdetails
#2ACCEPTED0.58 sdetails

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:53:23: warning: comparison of integer expressions of different signedness: 'int' and 'uint32_t' {aka 'unsigned int'} [-Wsign-compare]
   53 |     for (int i = 0; i < n; ++i) {
      |                     ~~^~~
input/code.cpp:62:23: warning: comparison of integer expressions of different signedness: 'int' and 'uint32_t' {aka 'unsigned int'} [-Wsign-compare]
   62 |     for (int i = 0; i < q; ++i) {
      |                     ~~^~~

Code

#include <iostream>
#include <vector>
#include <numeric>
#include <cstdint>

uint32_t find_power(uint32_t n) {
    n--;
    n |= n >> 1;
    n |= n >> 2;
    n |= n >> 4;
    n |= n >> 8;
    n |= n >> 16;
    n++;
    return n;
}

uint32_t p_n;

uint64_t build_segment_tree(std::vector<uint64_t> &tree, uint64_t idx) {
    if (idx < p_n) {
        tree[idx] = build_segment_tree(tree, 2*idx) ^ build_segment_tree(tree, 2*idx+1);
    }
    return tree[idx];
}

void update(auto &tree, uint64_t idx, uint64_t value) {
    idx += p_n;
    tree[idx] = value;
    for (idx /= 2; idx >= 1; idx /= 2) {
        tree[idx] = tree[2*idx] ^ tree[2*idx+1];
    }
}

uint64_t get_xor(auto &tree, uint64_t a, uint64_t b) {
    a += p_n;
    b += p_n;
    uint64_t sum = 0;
    while (a <= b) {
        if (a%2 == 1) sum = tree[a++] ^ sum;
        if (b%2 == 0) sum = tree[b--] ^ sum;
        a /= 2;
        b /= 2;
    }
    return sum;
}

int main() {
    uint32_t n, q;
    std::cin >> n >> q;
    p_n = find_power(n);

    std::vector<uint64_t> segment_tree(p_n*2, 0);
    for (int i = 0; i < n; ++i) {
        uint64_t e;
        std::cin >> e;
        segment_tree[p_n+i] = e; 
    }

    build_segment_tree(segment_tree, 1);
    std::vector<uint64_t> outputs;

    for (int i = 0; i < q; ++i) {
        uint32_t a, b;
        std::cin >> a >> b;

        outputs.push_back(get_xor(segment_tree, a-1, b-1));
    }

    for (auto output : outputs) {
        std::cout << output << std::endl;
    }
}

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
...