Why I got Runtime Error on first test w/o vector reserve and got Accepted with reserve?
The only difference is line 77 (if you open it in text editor).
Also, it passes test on local machine even without reserve statement.
RE
ImplicitSegmentTree(int l, int r) {
lb = l; rb = r;
n = r-l+1;
next = 0;
// TODO Change
// nodes.reserve(4831707);
nodes.push_back(Node());
root = &nodes[next++];
}
OK
ImplicitSegmentTree(int l, int r) {
lb = l; rb = r;
n = r-l+1;
next = 0;
// TODO Change
nodes.reserve(4831707);
nodes.push_back(Node());
root = &nodes[next++];
}
And last: the memory limit isn't a problem with this solution, because even with reserve(1e7) it works fine.
This is because of the way how vectors work. When you increase the size of a vector, it sometimes needs to relocate all of its elements to a different place in memory. When this happens, all pointers to its elements may become invalid. Using reserve means that until the vector size reaches some threshold (which is not less than the number of elements you reserved), it won't be relocated, that's why it works with reserve.
Do the vectors reallocate new memory for every push_back when a size is a power of two? I knew that vectors are contiguous in memory but did not understand how its allocation (towards a power of two) actually works. Is this "power of two" allocation just a method to guarantee $$$O(\frac{2^n}{2^{n-1}})=O(1)$$$ amortized time complexity?
Yes, but it is unspecified whether the implementation needs to reallocate when their size is a power of 2; only the specifications in the C++ standard are relevant. You can use any exponential reallocation scheme for getting amortized $$$O(1)$$$ complexity.
If you want your code to work as it is, you can consider using a
std::dequeinstead of astd::vector. It supports pretty much all vector operations you would need in this context and doesn't suffer from pointer/iterator invalidation. Keep in mind that an emptystd::dequeis quite large though.Thx, never heard about relocation, because never worked with pointers in such way.