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?
In your conditional, we have an lvalue on the true branch and a (p)rvalue on the false branch, and according to C++ standard for the ternary operator, the final value category of const auto& shuold have the same type (in this context, look at the sequence in stages), so I think the vector from the map gets copied to a prvalue object with lifetime inside the loop, which should be slow.
thank you! it makes sense now, will be careful when using ternary operator from now on :)