In problem 1167C, this submission gets a TLE. However, changing the line
ele = unordered_set<lli>(); gets an AC. Why does that happen? I read the docs and
std::unordered_set::clear has complexity "linear in the size of the container, i.e., the number of elements". We know that the container
ele's size won't exceed
n, the total number of elements. Thus, the total cost of clear operations does not exceed
n. So, it just adds an extra complexity of
n to my original code. At max, my code execution time should double, however, my AC code takes 499ms, so the code with
.clear() shouldn't have taken more than around 1sec in any circumstances.
Could anyone help me understand the problem here?