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


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