If I use unordered_map<int,multiset> to store the values, it gives a TLE. In the same code, if I change it to unordered_map<int,vector>, and sort the map's value when taken into use (to act like multiset), doesn't give a TLE. How/Where is the time complexity different for both ?
P.S. — Pardon me if I did not follow the conventions of a blog, this being the first one. Would be happy to know about my mistakes.
The constant factor of unordered_map is better than that of map.
You can use PBDS hash tables for even faster performance.
multiset has insert in $$$O(log(n))$$$, while vector has O(1) push_back. Multiset insert, Vector push_back