DRWLNS - Drawing Lines


John is a bit upset now. Today was his chemistry central viva and it did not go very well. So to cheer up he bought a notebook, a pencil and an eraser.

In the note book there are N points drawn in a row. The points are numbered from 1 to N serially.

Now, John decided to do a strange thing with those points.

At each moment, John puts his pencil or eraser at a point A and drags it to point B. As a result, some line segments may be created.

And then, Sometimes he stops and thinks of a point C and tries to find out if point C is on a line segment or not.

You have to solve a similar problem.

 

INPUT:

First line of the input will contain two integers N (1<=n<=109) and M (1<=M<=105) where N denotes number of points and M denotes number of queries.

Then M line follows. Each line contains a query.

Each query will be one of the following forms:

0 A B: which means an eraser has been dragged from point A to point B.

1 A B: which means a pencil has been dragged from point A to point B.

2 C: which means you are asked to answer the state of point C. There will be at least one query of this type.

(It is guaranteed that A<=B and 1<=A, B, C<=N)

OUTPUT:

For each query of the form “2 C”, print a single line.If point C is NOT on any line segment then print -1.

Otherwise, print the start and end point of the segment.

See sample input/ sample output and explanation for details.

Sample Input

Sample Output

25 14

2 10

1 20 25

1 9 13

2 12

2 7

1 11 21

2 15

0 17 20

0 22 25

2 21

2 5

1 1 8

2 12

2 4

-1

9 13

-1

9 25

21 21

-1

9 16

1 8

 

Explanation:

In the 1st query, there are no line segments. So point 10 is not on any segment.

After 2nd query, there is 1 line segment: [20, 25].

After 3rd query, there are 2 line segments:  [9, 13], [20, 25].

In the 4th query, point 12 is on [9, 13] segment.

In the 5th query, point 7 is not on any segment.

After 6th query, there is 1 line segment [9, 25]. ([9, 13], [11, 21] and [20, 25] segments will merge into only 1 segment).

In the 7th query, point 15 is on [9, 25] segment.

After 9th query there are 2 segments: [9, 16] and [21, 21].

In the 10th query, point 21 is on [21, 21] segment.

In the 11th query, point 5 is not on any segment.

After 12th query there are 3 segments: [1,8],[9, 16] and [21, 21].

In the 13th query, point 13 is on [9, 16] segment.

In the 14th query, point 4 is on [1, 8] segment.

 


hide comments
mamedov_1: 2016-09-07 11:16:47

What will happen if we have queries like (1, 1, 10), (0, 5, 5), and (1, 5, 5)? Do we remain with line segments [1, 4], [5, 5], and [6, 10] or we will have only one segment [1, 10]?

mahmud2690: 2016-08-15 20:26:40

@Md. Najim Ahmed, can you check submission 17512434, i can't figure out why i'm getting WA.

mehmetin: 2016-01-06 12:37:52

@Najim: That's right, the overall complexity is O(N log N), although one query can go up to O(N) . Thanks, it's clear now.

Md. Najim Ahmed: 2016-01-06 11:31:48

@mehmetin: At first thought it would seem so.
But actually the complexity reduces to O(N log N) where N is number of queries.
Think it like this,
what is the highest number of disjoint segment than can be inserted into a set (red black tree) after all the queries ?
the answer in N.
Now what is the highest number of elements that can be deleted from the set after all the queries ?
the answer is also N.
so overall 2N element is either inserted ot deleted.
hence, Complexity reduces to O(N log N)

if it is still unclear i would like you to notice the fact that number of element in the set only increases for the draw query and the increment is highest 1 element.
and for erase query or whenever a merging happens number of element always reduces.

Last edit: 2016-01-09 10:16:30
mehmetin: 2016-01-05 15:45:11

@Najim & @Yogendra: Are you sure this problem can be solved in O(log N) per query? I got accepted using set like data structure from Boost, and it seems like it goes to O(N) per query in the worst case, N being the total number of segments that must be merged in an update operation.

Last edit: 2016-01-05 15:59:43
Yogendra Kumar: 2015-12-28 23:18:44

Thanks Md. Najim Ahmed! got your hint a little late but I did it finally. Awesome feeling to be the first java solver.
And sorry, time limit is perfect :)
I had to do it in O(log n) per query to get accepted.

Last edit: 2015-12-28 23:22:54
Md. Najim Ahmed: 2015-12-18 07:16:39

#Hint: Use Set like Data structure to reduce it to M*log2 (N) :)

Yogendra Kumar: 2015-12-15 23:25:45

@Md. Najim Ahmed, Thanks for the explanation.
BTW time limit is too strict for java, my java solution using segment trees (Complexity: O( log n ) for '0 A B' & '1 A B', O( (log n)^2 ) for '2 C') is getting TLE. You might want it to relax a bit for java :P

Md. Najim Ahmed: 2015-12-15 16:13:27

i don't see why there should be a confusion about that .
You can interpret it as a single dot (A/B) is erased and a single dot (A/B) is drawn
See the 10th query to understand

Last edit: 2015-12-15 16:14:18
Yogendra Kumar: 2015-12-15 12:54:50

What is expected from operations 0 A B and 1 A B when A == B ?


Added by:Md. Najim Ahmed
Date:2015-12-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY