Editorial for The Contest Contest 1 P2 - A Typical CCC Senior Problem
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
Under this constraint, the process can be simulated using a stack:
For each possible value of from
to
, iterate through all numbers in the array and push them into a stack. When the current number is
, skip the pushing and remove the last
elements from the stack. The answer is the sum of elements that are remaining in the stack.
Subtask 2
This subtask is meant to reward suboptimal implementations of the full solution.
Subtask 3
For each from
to
, we can solve the problem in reverse to calculate the sum of elements that will be removed from the array. In particular, for each value of
from
to
, we iterate through their occurrences in reverse order while keeping track of the interval of elements that are removed.
Suppose we are at some position and the left endpoint of the interval is
. There are two cases:
- Case 1:
In this case, the elements in the intervalare intact, so we add the sum of those elements to the answer. We set our new value of
to be
.
- Case 2:
In this case, we have to remove some additional elements before index. To account for this, we set our new value of
to be
. This has the effect of "merging" two intervals of removed elements.
Using a prefix sum array, we can calculate the sum of elements in an interval in time and since each position is visited at most once, this gives us our desired time complexity.
Comments