Segments and Queries
Time limit1sMemory limit512 MB
Process up to 100 queries that add intervals of strictly increasing length and ask whether two added intervals are connected by the overlap-based move relation.
- Level
Medium5 of 10
- Topics
- Graph, Union-find, Implementation, Intervals
- Solved
- No attempts yet
Problem
Given N queries, perform each query. There are 2 kinds of queries, described below. Initially the set is empty.
1 x y(x < y): add the new segment (x, y) to the set. The size of a segment is greater than the size of any previously added segment.2 a b(a ≠ b): print 1 if there is a path from the a-th added segment to the b-th added segment, and 0 otherwise. The first added segment is segment 1.
To move from segment (x1, y1) to segment (x2, y2), we need x2 < x1 < y2 or x2 < y1 < y2. A path from segment I1 to segment I2 exists when you can get from I1 to I2 using only segments that were added to the set.
Input
The first line contains the number of queries N (1 ≤ N ≤ 100).
The next N lines contain one query each. Every value in the input is an integer whose absolute value is at most 109. A query of type 2 comes only after at least 2 queries have added segments to the set.
Output
For each query of type 2, print the result.