I submitted this 311120546 solution to the recent contest Educational Codeforces Round 176 (Rated for Div. 2).
I was pretty sure my solution is N^2, and I didn't see a reason why it should TLE. Right after submitting I was a bit surprised that the solution took like 1.5s but I thought whatever, there's no way it gets TLE.
How come this code takes over 2s? The only explanation I can see is that the iteration over multiset is not linear which is what I thought for quite a long time.
UPD1: The TLE is because of using a list??? When I use a vector instead, it passes in 500ms
Auto comment: topic has been updated by Filikec (previous revision, new revision, compare).
[redacted because i was wrong]
But I'm not sorting the list
I take that back apparently sorting lists is actually $$$O(n\log{n})$$$ time
Why would someone ever use lists in CP when vectors do exist?
To be honest I never found a problem that can be solved with a list and not be solved with the other data structures.
Thats because there are so low amount of problems that can be solved w lists
Generally if a problem can be solved in much lesser time complexity then there will be a test — case that pushes the unoptimized codes/approaches to TLE. It was supposed to be done in O(n log n), using either sorting or Max-Heap. N^2 is much more complex. That's why it resulted in TLE.
Also about list vs vector, list uses linked list which has higher access complexity. Vector has O(1) due to indexing.
The main reason for TLE here is not that “iteration over multiset” is itself nonlinear, but that the algorithm has many container operations implemented via structures with logarithmic overhead and poor cacheability. While it takes O(1) per step to search through the elements in a container (e.g., multiset), the insert, delete, and search operations in these structures (based on balanced trees) take O(log n) time. If you search k elements in each pass of the outer loop (and k can be comparable to n), the total complexity increases to about O(n*k*log n) or even O(n²) in the worst case.