Canadian Computing Olympiad: 2020 Day 2, Problem 2
Altina is starting an interval collection. An interval is defined as two positive integers such that
. We say that the length of this interval is
. Additionally, we say that an interval
contains another interval
if
and
. In particular, each interval contains itself.
For a non-empty set of intervals, we define the set of common intervals as all the intervals
that are contained within every interval
in
. If the set of common intervals is non-empty, then we say the greatest common interval of
is equal to the common interval with the largest length.
For the same set , we define the set of enclosing intervals as all the intervals
that contain every interval
in
. Note that this set is always non-empty, so we say the least enclosing interval of
is equal to the enclosing interval with the smallest length.
Initially, Altina owns no intervals in her collection. There are events that change the set of intervals she owns.
The first type of event is when Altina adds an interval to her collection. Note that this interval could have the same
as another interval in her collection. They should be treated as separate intervals.
The second type of event is when Altina removes an existing interval from her collection. Note that if Altina has more than one interval with the same
, she removes exactly one of them.
After each event, Altina chooses a non-empty subset of intervals she owns in her collection that satisfy the following conditions:
- Among all sets
Altina could choose, she chooses one that has no greatest common interval, if possible. If this is impossible, then she chooses one which has the length of its greatest common interval as small as possible.
- Among all sets
that satisfy the previous condition, she chooses one which has the length of its least enclosing interval as small as possible.
Your task is to determine the length of the least enclosing interval of the set Altina chose after each event.
Input Specification
The first line of input contains
, the number of add and remove operations in total. The next
lines are in one of the following forms:
A l r
: add the intervalto Altina's collection.
R l r
: remove one of the instances of the intervalfrom Altina's collection. It is guaranteed the interval to be removed exists and that the collection will be non-empty after the interval is removed.
For all subtasks, .
For 3 of the 25 marks available, .
For an additional 8 of the 25 marks available, .
For an additional 7 of the 25 marks available, .
For an additional 4 of the 25 marks available, the following condition holds after each event: for every two separate intervals and
in Altina's collection, either
or
.
Output Specification
The output consists of lines, each line containing the length of the least enclosing interval for Altina's choice of
as described in the problem description.
Sample Input
5
A 1 5
A 2 7
A 4 6
A 6 8
R 4 6
Output for Sample Input
4
6
5
4
7
Explanation of Output for Sample Input
After the interval is added, there is only one interval, so
is the only valid choice and the least enclosing interval is
.
After the interval is added,
has the greatest common interval
and least enclosing interval
.
After the interval is added,
has the greatest common interval
and least enclosing interval
.
After the interval is added,
has no greatest common interval and its least enclosing interval
.
Note that
also has no greatest common interval but its least enclosing interval
has a greater length than
.
After the interval is removed,
has no greatest common interval and least enclosing interval
.
Comments