시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 104 | 8 | 6 | 28.571% |
N개의 쿼리가 주어졌을 때, 쿼리를 수행해보자. 쿼리는 총 2가지 종류가 있고 아래와 같다. 가장 처음에 집합에는 아무것도 없다.
1 x y
(x < y): 새로운 구간 (x, y)를 집합에 추가한다. 구간의 크기는 이전에 추가된 구간의 크기보다 크다.2 a b
(a ≠ b): a번째 추가된 구간에서 b번째 추가된 구간으로 이동하는 경로가 있으면 1, 없으면 0을 출력한다. 가장 처음 추가된 구간은 1번째 구간이다.구간 (x1, y1)에서 구간 (x2, y2)로 이동하려면 x2 < x1 < y2 또는 x2 < y1 < y2를 만족해야 한다. 구간 I1에서 I2로 이동하는 경로가 있다는 것은 I1에서 I2로 집합에 추가된 구간만을 이용해서 이동할 수 있을 때이다.
첫째 줄에 쿼리의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.
둘째 줄부터 N개의 줄에 쿼리가 한 줄에 하나씩 주어진다. 입력으로 주어지는 모든 값은 절댓값이 109보다 작거나 같은 정수이다. 2번 쿼리는 적어도 2개의 쿼리가 집합에 추가된 이후에 주어진다.
2번 쿼리가 주어질 때마다 결과를 출력한다.
5 1 1 5 1 5 11 2 1 2 1 2 9 2 1 2
0 1