Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link ×

shivansh20's blog

By shivansh20, history, 9 months ago, In English,

In problem 1167C, this submission gets a TLE. However, changing the line ele.clear(); to 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?

Read more »

  • Vote: I like it
  • +55
  • Vote: I do not like it