Why this code gets TIme limit exceeded?

[better_sleep]

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?

[ssjgz]

Try replacing:

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

with

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:

@cppreference

Complexity

On average, logarithmic in the distance between first and last: Performs approximately log_2(N)+1 element comparisons (where N is this distance).
On non-random-access iterators, the iterator advances produce themselves an additional linear complexity in N on average.

(emphasis mine).

[better_sleep]

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