Editorial for COCI '21 Contest 2 #5 Osumnjičeni
Submitting an official solution before solving the problem yourself is a bannable offence.
The first observation is that for each question, the optimal sequence of lineups can be built by starting from the suspect and adding the suspects one by one from left to right into the current lineup, until at some point this is not possible. When we reach such a suspect that can't be added, we start a new lineup and repeat this process until we reach the suspect
.
We can think of this in the following way: for each index
, define
, which will denote the smallest index greater than
such that the suspects from
to
don't form a valid lineup. In other words, if we start building a lineup from
,
is the first suspect we won't be able to add into our set, and he represents the start of a new lineup.
The answer to each query now reduces to finding out how many times must we iterate the function , starting from
until we pass
, that is, so that
. The solution to this problem has two parts: how do we efficiently calculate
for each index
, and then how to answer the queries efficiently.
can be calculated with the "two pointers" idea. Notice that if
, then
because when moving from index
to
, the lineup we have built thus far remains valid even after we remove
from the lineup, and possibly it should be extended to the right. To make the insertions and deletions from the current lineup efficient, we have to use a data structure which can support these operations quickly. It is sufficient to use a set container from C++ STL, in which we'll store the left boundaries of the currently inserted height ranges. When inserting a new interval
, we find the leftmost left boundary that is to the right of
(using the
lower_bound
function) and check that it isn't in the interval . Analogously, we can find the rightmost left boundary smaller than
and check that
isn't contained in that interval. If the mentioned conditions hold, we can add the current suspect to the lineup and add the left boundary to the set.
We can answer the queries using "binary lifting". We'll use to store
, where
is being applied
times. Notice that for all indices
it holds that
, and also
. Using the mentioned formulas, we can calculate
for all
, and
. We can now answer each query in
by descending over
and at each step moving to the
-th ancestor if it does not pass the right boundary (
) of the current query.
The total time complexity of the presented algorithm is . The subtasks were meant for competitors who managed to figure out how to calculate
efficiently, or who knew how to answer queries quickly, but who didn't know both.
Comments