I submitted the same solution on two c++ compilers g++ 17 and g++ 20 . On g++ 20 my solution ran quite fast and got ac in 200ms . on the other hand on g++ 17 it got TLE with 2000ms runtime . I dont know whether the issue is with the time complexity of my solution or the compiler?
here is the link for the problem : https://mirror.codeforces.com/contest/1654/problem/C
here are my submissions: (AC) https://mirror.codeforces.com/contest/1654/submission/288743518
(TLE) https://mirror.codeforces.com/contest/1654/submission/288743107
This works: https://mirror.codeforces.com/contest/1654/submission/288782927
Replaced existence check from
s1.count(n)tos1.find(n)because you were calling alreadys1.erase(s1.find(n))insideifstatement.I dont think it should give TLE?
If you think about it you don't need the actual count of elements equal to $$$n$$$ but instead you just need to remove the first one of the many elements equal to $$$n$$$.
Read this blog on how $$$count$$$ performance in the case of $$$multiset$$$ might become $$$O(n^2)$$$ when you have a lot of elements equal to $$$n$$$.
I'm not surprised in later implementations of the standard library they decided to improve $$$count$$$ performance on pathological edge-cases with many equal elements
I didn't knew it. Thanks for sharing . I was in habit of using count and it never gave me TLE in case of sets but here it was multiset and I didn't noticed that.