Even though code is same one gives tle while one gives ac

Why does this submission -> https://www.codechef.com/viewsolution/27653355 give tle
while this one -> https://www.codechef.com/viewsolution/21727883 gives ac.

According to me they both have same time complexity and are pretty much the same except i am using a map and he has used an array in hash table. Please explain

Use unordered map it will solve your problem

2 Likes

Always be careful while using STL map. Because the map takes approx O(logN) time for each operation. So the total complexity is actually of the order O(N^2logN) which might give TLE for this problem.

Changing map<int> to unordered_map<int> is enough to get AC here because you don’t need the keys to be stored in sorted order.

1 Like

Thanks i got an ac after that