Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Good and Evil

By Peregrine_Falcon · Limits 1s, 512 MB

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.
~Eric Burdon

Unlike human beings, segments have a fixed part of good and evil.
Let’s take a segment from LL to RR for example. Let MM == ((L+R)/2)\lfloor{((L+R)/2)}\rfloor rounded down to nearest integer point. The part LL to MM is good and the rest of the segment is evil.

Initially, you have an empty collection of integer segments. You have to perform QQ operations of three types in the collection:

Type 1: Add a segment from LL to RR to the collection.
Type 2: Remove an existing segment from LL to RR 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 XX, find the number of good and evil parts of segments is intersected by point X.


The first line of input consists of an integer QQ (3Q2×105)(3 \leq Q \leq 2×10^5) number of operations to be performed.
Each of the next QQ lines consists of one of three types of operations.
Type 1: 11 LL RR (1L<R1016)(1 \leq L < R \leq 10^{16}).
Type 2: 22 LL RR (1L<R1016)(1 \leq L < R \leq 10^{16}).
Type 3: 33 XX (1X1016)(1 \leq X \leq 10^{16}).

For 40 Points: 1Q,L,R1031≤ Q,L,R ≤10^3
For 100 Points: Original constraints.


For each of the Type 3 queries, output two integers GG and EE separated by space in each line. GG is the number of the good segments and EE is the number of evil segments that point XX is part of.


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.
The second operation adding another segment from 3 to 9. Here, 3 to 6 is good and 7 to 9 is evil.
The third operation is a query for point 6. Point 6 is intersecting with the first segment’s evil part and the second segment’s good part.



65% Solution Ratio

user.545264Earliest, 5M ago

Nasif_44thFastest, 0.1s

prajjwal07Lightest, 14 MB

Md_AbdullahShortest, 1571B


Login to submit


First, we need to compress all the numbers given in the input. We will save all the update and query...

Toph uses cookies. By continuing you agree to our Cookie Policy.