Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link ×

Undefined behavior when writing persistent segment tree

Revision en2, by ouuan, 2019-12-06 14:14:04

Today, I spent a whole afternoon solving 786C - Till I Collapse, because of undefined behavior.

The origin code is here: 66394911. It seems pretty well, but can't even pass the sample tests.

However, after adding one line (t.reserve(5000000);) it passed: 66394938.

For those who don't want to read my codes, here is a shorter one:

#include <iostream>
#include <vector>

using namespace std;

vector<int> bar;

int foo(int p)
    int x = bar.size();
    if (p == 0) return x;
    bar[x] = foo(p - 1);
    cout << bar[x] << ' ';
    return x;

int main()
    bar.resize(1, 0);
    return 0;

Can you guess the output?

The output

The reason


  Rev. Lang. By When Δ Comment
en2 English ouuan 2019-12-06 14:14:04 4 Tiny change: '.\n\n2. Be aware of it' -> '.\n\n2. Beware of it'
en1 English ouuan 2019-12-06 14:09:21 2036 Initial revision (published)