## CCO '20 P5 - Interval Collection

View as PDF

Points: 25 (partial)
Time limit: 3.5s
Memory limit: 1G

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 interval to Altina's collection.
• R l r: remove one of the instances of the interval from 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 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 .