CPP Register - The key behind AC

[smile_forever]

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:
TLE _{^{20 pts}}
AC _{^{100 pts}}

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

[hetp111]

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

[smile_forever]

Oh yes, that can save few seconds. Thanks.

[s5960r]

Or simply change it to unordered_map

[smile_forever]

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.

[smile_forever]

@smile_forever

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?

[hetp111]

That’s because unordered map have worst time complexity on O(n).
Check this:

Blowing up unordered_map, and how to stop getting hacked on it - Codeforces

[smile_forever]

Thanks for clarification.

[s5960r]

That’s true ! However unordered_map worked for this one

[smile_forever]

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.