Abhi_Sarkar1996's blog

Please help.Reason For TLE
By Abhi_Sarkar1996, history, 7 years ago, In English

Hello guys. I was solving this problem http://mirror.codeforces.com/problemset/problem/620/C by using maps. Got TLE on test 42 here http://mirror.codeforces.com/contest/620/submission/29965143 . What I am confused about is the testcase 32 and 42 are similar so why is it giving ac on the first and TLE on the second? Any help will be much appreciated.

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

used std::map instead of std::unordered_map,AC,i dont know why!

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    unordered_map doesn't always work in O(1) complexity, it's O(1) for small data inputs, there are specific cases for wich the worst case is O(N) per query/update, whereas an map isn't a hash data structure, it's a binary search tree(i think the STL one uses a red-black tree), wich has a worst case complexity for query/update of O(log2(N)). if the testcase is built in a very specific way, the map can work way better in practice than the unordered_map. one way to get ac with unordered_map would be to change the hash function to something else or more simply just write your own Hash data structure it's very easy and simple to do so.

    → Reply