hustler_72's blog

Is map better than unordered_map in terms of time for big numbers???
By hustler_72, history, 2 years ago, In English

Hello everyone!

Today I found a weird thing. I was solving problem C from Educational Codeforces Round 115. The link for the same is here. 1598C - Удаление двух элементов I have solved this problem using map. The link to my solution using map is here: map solution But it was consuming more time. So I decided to reduce it. Then I realized that I actually do not want the ordered map. So, I have just replaced map with unordered_map. The link to my solution using unordered_map is here: unordered_map solution But surprisingly, I got TLE on test case 14. I don't know the reason behind this. Can anyone explain me why this happened?

Thank you :)

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

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

map guarantees the TC of O(log n) while unordered_map may go to O(n) for some inputs, and there are different ways to deal with that.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

dfghjkolp;lkjhgfghju

→ Reply
»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

this

→ Reply