I saw a question on codechef,where I used multiset of pairs to solve the problem which gave me TLE(time limit exceeded) but when i submitted the exactly same code with the set of pairs instead of multiset of pairs I got a correct answer verdict AC. I am thinking that the problem with multiset is occuring at the time of input.Is there any difference between the sorting algorithm of set and multiset?or is there anything else which is giving me TLE…Just want to remind again that all the things in my both codes were same except the use of set and multiset…Please help.
u shld hav posted link to ur solution
I think std::multiset has a bigger constant factor than std::set.
Will that diffrence become so large that it will cross 2 sec time limit when the set is performing the same in 0.34 sec?
Oh that’s a big difference. I don’t know what could the reason be then.
Upload the problem link and your solution link
Question link
Solution using multiset of pairs giving tle using binary search
https://www.codechef.com/viewsolution/23899493
Solution using multiset of pairs using find function giving AC
Binary search function on a set has a higher complexity because you can’t access a index in constant /logN time in a set or multiset.