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.net/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 ?