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.
Submission #21097535 - Codeforces
Can anyone please help me figure out why this happens?
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.)
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.
Thanks a lot for sharing that information!
I didn’t knew about that