Why this code gets TIme limit exceeded?

My code : Submission #78299807 - Codeforces

I tried to optimize my removing auto, not using long long int everywhere.

Whereas this code using two sets and much more erase and insert operations, gets accepted.

Accepted code: Submission #21097535 - Codeforces

Can anyone please help me figure out why this happens?

Try replacing:

set<int>::iterator leftit = lower_bound(killed.begin(), killed.end(), index);
set<int>::iterator rightit = upper_bound(killed.begin(), killed.end(), index);


set<int>::iterator leftit = killed.lower_bound(index);
set<int>::iterator rightit = killed.upper_bound(index);

(the latter is asymptotically faster - std::lower_bound(killed.begin(), killed.end(), index) will be linear time since std::set::iterator is not a random-access iterator. killed.lower_bound(index); is logarithmic, though.)

From here:

(emphasis mine).


Thanks a lot for sharing that information!
I didn’t knew about that :slight_smile:

1 Like