So I was solving F. Ant Colony and got TLE on test 65. I didn’t know the reason, even though I believed time complexity was q log n.

Here's the submission

I tried replacing map with unordered_map, still no luck. It turned out that this line was causing the TLE:

const auto &v = idx.count(gc) ? idx[gc] : vector<int>();

When I replaced it with:

if (!idx.count(gc)) {
    ans[i] = r - l + 1;
    continue;
}
const auto &v = idx[gc];

It passed with 203ms

I thought that creating an empty vector every time was the problem but when I deleted the if (!idx.count(gc)) part it still passed with 296ms even though this should be identical to what I did in the first submission which is creating a key in idx and initializing an empty vector :D

Im confused

Could someone explain why the first code TLE’d while the second one didn’t please?