Today I tried to solve Problem D(div2) of last Contest ( Codeforces Round 310 (Div. 2) ). In this problem I used lower_bound() function on a set of pair of pair and int ( set< pair< pair<long long, long long> , int > > ). Here is my ACed submission 11834954 and my TLE submission 11835029 . I don't know why I get TLE in second code. :S
Ok, Let me explain what I 've done here, I have a set like set< pair< pair<long long, long long> , int > > bridges on which I tried to apply lower_bound() function ( in line number 171 in my both code ). In first submission I used lower_bound() as like bridges.lower_bound(make_pair(keyValue,0LL)) and I got AC. But in my second code I used lower_bound() as like lower_bound(bridges.begin(),bridges.end(),make_pair(keyValue,0LL)) and I got TLE on case 11.
What is the difference between calling lower_bound() function in above mentioned 2 way ?
Auto comment: topic has been updated by sonjoydabnath (previous revision, new revision, compare).
Unfortunately,
lower_bound(set.begin(), set.end(), x)works in O(N). Useset.lower_bound(x)to reach O(logN) complexity.can you plz explain why it works in O(N) ? Is this O(N) complexity only applied for set ? I used lower_bound in this way with vector but got Aced in many problems?
Read about random-access iterators :) Briefly: in set you can only increment or decrement it, but in vector you are able to take (lo+hi)/2.
what about this soln 11833491 ? here I used vector instead of set and got TLE...
I never told vector is better than set :) Of course, it depends on problem. I'm not sure, but I think in this code your trouble is in erase(). According to this it is linear in time. So, your algo works in O(n^2) in this case. By the way, erase(position) in set is amortized constant (link).
As Totktonada said above, std::vector uses random access iterators, that allows you to access any element directly.
Std::set uses bidirectional iterators, and you can only go forward or backward using it (you cannot access elements directly).