I was solving this November Lunchtime 2017 problem: https://www.codechef.com/problems/LRQUER and after getting a lot of TLEs, I learned the following:
std::lower_bound(<container>.begin(), <container>.end(), query) and <container>.lower_bound(query) does not always have the same time complexity.
To be specific, in containers that support Random Access Iterators (std::vector, std::array, etc.), they’ll have the same time complexity but not if the container don’t support them (std::set, etc.). I was using std::multiset in my solution.
Please read this comment in Codeforces to learn more: http://codeforces.com/blog/entry/20553?#comment-252670
This is also mentioned in Complexity section of std::lower_bound() in cppreference website: http://en.cppreference.com/w/cpp/algorithm/lower_bound