Hi. I want to preface this by saying i am a noobie and i totally understand if i am missing something obvious here , but i have seen that the vector object in c++ is way too efficient. What do i mean by way too efficient ? I mean that — even solutions which should be O(N^2) complexity tend to run within 1 second.

An example submission where this is happening —

Example: https://codeforces.me/contest/1883/submission/241050682

Consider the code snippet —

for(int i=0;i<n;i++)
        {
            auto it = lower_bound( a.begin(), a.end(), b[i] );
            it--;
            if(it >= a.begin())
            {
                int val = *it;
                if( val < b[i] )cnt++;
                a.erase(it);
            }
        }

This code snipped from above submission is finding a lower bound in vector A, and then erasing the element. In the worse case, erase should have complexity O(N), which means that the loop overall should have complexity O(N^2)

see this gfg article which https://www.geeksforgeeks.org/vector-erase-and-clear-in-cpp/ where it says clearly that erase is O(N) worst case

Can someone help me understand how the heck its so dang efficient ?