Inside each of us, there is the seed of both good and evil. It's a constant struggle as to which one will win. And one cannot exist without the other.
Unlike human beings, segments have a fixed part of good and evil.
Let’s take a segment from to for example. Let rounded down to nearest integer point. The part to is good and the rest of the segment is evil.
Initially, you have an empty collection of integer segments. You have to perform operations of three types in the collection:
Type 1: Add a segment from to to the collection.
Type 2: Remove an existing segment from to from the collection. It is guaranteed that the input segment exists in the collection. If there are multiple copies of the same segment, only one will be removed.
Type 3: Given integer point , find the number of good and evil parts of segments is intersected by point X.
The first line of input consists of an integer number of operations to be performed.
Each of the next lines consists of one of three types of operations.
Type 1: .
Type 2: .
Type 3: .
For 40 Points:
For 100 Points: Original constraints.
For each of the Type 3 queries, output two integers and separated by space in each line. is the number of the good segments and is the number of evil segments that point is part of.
7 1 1 9 1 3 9 3 6 3 5 2 3 9 3 9 3 10
1 1 2 0 0 1 0 0
The first operation is to add a segment from 1 to 9. Here from 1 to 5 is good and 6 to 9 is evil.
Login to submit
First, we need to compress all the numbers given in the input. We will save all the update and query...