In the last educational round, my below solution for the problem 2004D - Colored Portals got TLE.
TLE solution: 276676175
After the contest, I submitted the solution with only one line of change in code and it got AC.
AC solution: 276725505
The only difference between both the codes is:
In the TLE solution:
for (auto x : mp)
And in the AC solution:
for (auto x = mp.begin(); x != mp.end(); x++)
Anyone, please help me to find out the time complexity of each statement. And why this first one gives TLE?
Which statement should be preferred to avoid this type of situation?
Doing
for(auto x : mp)makes you copy the wholemapwhen processing it, thus increasing the complexity per query to $$$O(n)$$$ instead of $$$O(log(n))$$$. A solution would be usingfor(auto &x : mp).Thanks.