tanvir942316's blog

C. Removing Smallest Multiples........ Am I getting TLE because of using map?
By tanvir942316, history, 2 years ago, In English

Why my solution of C is getting TLE. Can anyone tell me please? Isn't it supposed to pass?

Is this happening because of using map. Please help me. I have to know this.

https://codeforces.me/submissions/tanvir942316

→ Reply

  • Vote: I like it
  • -2
  • Vote: I do not like it

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

Yes. Using map will make your solution $$$O(n \cdot log^2 n)$$$.

Putting $$$n = 10^6$$$, number of operations = $$$4 \times 10^8$$$. You can use std::unordered_mapwhich gives constant time insertion and accessing on average ($$$O(n)$$$ in worst case). Your solution with unordered_map 173282698.

More (Getting AC with std::map but TLE with std::unordered_map)
→ Reply