Frog Jump
Time limit1sMemory limit512 MB
Given N disjoint horizontal line segments, two logs are connected if a vertical jump between them crosses no other log; answer queries on whether logs are reachable.
- Level
Hard8 of 10
- Topics
- Geometry, Union-find, Sorting
- Solved
- No attempts yet
Problem
N logs float on a pond, all oriented horizontally. A frog can jump from one log A to another log B in a direction that is exactly vertical. When jumping, it must not pass over any other log (endpoints included).
For example, in <Figure 1>, the frog can jump from log 1 to log 2 along the dotted line. After jumping from log 1 to log 2 and then jumping to log 3, the frog has moved from log 1 to log 3. (Walking along a log is always allowed.)
Given the positions of the logs, write a program that determines, for each queried pair of logs, whether the frog can travel from one log to the other using one or more jumps.
Input
The first line gives the number of logs N and the number of queries Q. The next N lines give three integer coordinates x1, x2, y for each log. The given log is the segment connecting the points (x1, y) and (x2, y), with x1 < x2. Every coordinate is between 0 and 109 inclusive. The logs are numbered 1 through N in the given order. Two distinct logs do not meet, not even at an endpoint. The next Q lines give the numbers of two distinct logs. (1 ≤ N ≤ 100,000, 1 ≤ Q ≤ 100,000)
Output
Print Q lines. Line i must contain the answer to the i-th query, in the given order. For the two logs in the query, the answer is 1 if the frog can travel from one log to the other using one or more jumps, and 0 otherwise.