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.
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)
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.
1 20 25
1 9 13
1 11 21
0 17 20
0 22 25
1 1 8
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.
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]?
@Md. Najim Ahmed, can you check submission 17512434, i can't figure out why i'm getting WA.
@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:
@mehmetin: At first thought it would seem so.
@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
Thanks Md. Najim Ahmed! got your hint a little late but I did it finally. Awesome feeling to be the first java solver.
Md. Najim Ahmed:
#Hint: Use Set like Data structure to reduce it to M*log2 (N) :)
@Md. Najim Ahmed, Thanks for the explanation.
Md. Najim Ahmed:
i don't see why there should be a confusion about that .
What is expected from operations 0 A B and 1 A B when A == B ?