C++ STL Map gives TLE when looping with auto?

I was working on this problem on CodeForces. My solution was giving TLE and I could not figure out why. Eventually I narrowed it to the faulty line and it was essentially the following

// map<int, set<long long>> res;
for(auto z : res) if(res[z.first].count(x)) res[z.first].erase(x);

This gives TLE on Test case 6. Now my res map has three keys at max (1,2,3). If I change the loop to-

for(int j = 1; j<=3; j++) if(res[j].count(x)) res[j].erase(x);

then the solution works and runs for all test cases. I want to understand why does the first loop not work and how to know when can I use that loop and when not?

Link to TLE submission. Link to correct submission. Only difference is in line 81-82.

>Solution :

for(auto z : res)

It copies the inner maps to z pairs each loop iteration. Try

for(auto& z : res)

Leave a Reply