tanvir942316's blog

By tanvir942316, history, 2 months ago,

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

 » 2 months ago, # | ← Rev. 2 →   +4 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)But it is possible to blow up unordered_map (to make access and insertion of order $O(n)$) by specific type of input. To prevent it you can use custom hash function.Read this for more details: Blowing up unordered_map, and how to stop getting hacked on itP.S: See how many people got hacked (see hacks made by beethoven97) because they used std::unordered_map.