I have just discovered, that std::set::lower_bound for larger sets is much-much faster than std::lower_bound.
Can anyone give explanation why does this happen?
Also, use std::set::lower_bound instead of std::lower_bound, I struggled on a problem for like 2 hours because of getting TLE for this.