CPP Register - The key behind AC

I’m trying too much to optimize my code for problem MSV, but it was TLE.
At last AC, when I used register keyword before (frequently used) variable.
Hope, this topics may help beginners like me.

Here is the submission link:
:timer_clock: TLE 20 pts
:white_check_mark: AC 100 pts

EDIT:
After changing map with gp_hash_table, it takes only 0.24 sec::
Updated Submission

Try using an array instead of map. It should work.

1 Like

Oh yes, that can save few seconds. Thanks.

Or simply change it to unordered_map :wink:

1 Like

I know that, But I’m too confused about using unordered_map. A solution was accepted when I used map but TLE when i used unordered_map.

Using Unordered_map :: TLE 2000ms+
Using map :: AC 342 ms
[ Just declaration is the difference between AC and TLE code ]

Would be appreciated if you look out and help.

Can you please explain it?

That’s because unordered map have worst time complexity on O(n).
Check this:
https://codeforces.com/blog/entry/62393

2 Likes

Thanks for clarification.

That’s true ! However unordered_map worked for this one :stuck_out_tongue:

1 Like

Yes, unordered map worked for this. But I found gp_hash_table faster than unordered_map. Here is the updated solution which take only 0.24 sec.

1 Like