One vector is not that slow. However, in your stl-vector code you allocate a million vectors! What happens then? Well, for each vector are allocated 3 pointers (begin, end and storage) as well as some elements for initial storage (this size doubles every time when reached). When you have a single vector that overhead is not that much, but when you have a million of them, it is terrifying.

Note: The same holds for other STL data structures as well — for example allocating a million priority_queues results in the same overhead.

OK with your code and STL vector: http://codeforces.net/contest/346/submission/4529404. You should add reserve to some small value if you're feeling that the worst test can got TLE, because there are too many reallocations on small vector sizes.

Thank you fmm! very nice.

Accidental today I read a text that related to your blog entry.I hope was attractive :

The sign of a mature professional is keeping the simple jobs simple. This is particularly challenging for those who are just learning a new subject. Medical students provide a classic example of this problem. After sitting through a few lectures on obscure tropical diseases, a young doctor worries that any patient with a sniffle and a rash might have the Ebola virus or bubonic plague, while a more experienced physician just sends them home with a bottle of aspirin.

Likewise, youmay have recently learned about balanced binary search trees, exception handling, parallel processing, and various models of object inheritance. These are all useful and important subjects. But they are not necessarily the best way to get a correct program working for a simple job.

To expand on the reserve suggestion. The issue with this code is not std::vector, it is push_back. Your custom vector uses static memory, so adding elements is trivial because the memory is already-allocated. std::vectors were designed to allow dynamic memory usage and resizing them.

A vector has a bunch of space allocated for it. Using push_back when the space is already-allocated is similar to your custom vector. But when push_back would make the required space bigger than the allocated space, vector needs to reallocate memory. I think that what really happens is that it reallocates twice of the memory it needs, so that the next n push_backs don't cause it. Reallocations are very expensive. In your code you have plenty of vectors and each of them has to reallocate multiple times.

reserve() makes it so the reallocation happens only once per vector and in order. But it brings a new issue, the memory is now static. In order to keep memory dynamic and be able to add elements without this issue, you could use another data structure. std::vector needs all of this issue because it is supposed to allow random access. In your code it seems that you don't need random access because you just iterate through the vectors.