시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2.5 초 (추가 시간 없음) 1024 MB 111 61 47 52.809%

문제

우주 정거장은 한 개의 선분으로 구성되어 있으며, 좌표 평면상에 $N$개의 우주 정거장이 있다. 각 우주 정거장은 $1$번부터 $N$번까지 번호가 붙어 있다.

비행선은 무조건 우주 정거장에서만 출발할 수 있으며 이동하면서 만나는 우주 정거장에서만 멈출 수 있다. 경계도 우주 정거장에 포함된다. 비행선이 움직이는 방법은 3가지다.

  • x축과 평행한 방향으로 이동.
  • y축과 평행한 방향으로 이동.
  • 우주 정거장 내에서 이동.

서로 다른 두 정거장이 주어졌을 때, 두 정거장 사이를 오갈 수 있는지에 대해서 알아보자.

입력

첫 번째 줄에는 우주 정거장 개수 $N$과 질문의 개수 $Q$가 주어진다. ($2 \le N \le 200\,000$, $1 \le Q \le 200\,000$)

다음 $N$개의 줄에는 $i$번 우주 정거장의 양 끝점을 나타내는 $x_{i,1}$, $y_{i,1}$, $x_{i,2}$, $y_{i,2}$가 주어진다. 모든 좌표의 절댓값은 $10^9$ 이하의 정수값이다.

다음 $Q$개의 줄에 서로 다른 우주 정거장의 번호 두 개가 주어진다.

출력

$Q$개의 줄을 출력한다. 각 줄에는 주어진 순서대로 질문에 대한 대답이 출력되어야 한다. 질문에 주어진 두 정거장 사이를 오갈 수 있는 경우 대답은 1, 그렇지 않은 경우 대답은 0이다.

예제 입력 1

3 3
5 5 1 1
4 7 6 7
7 2 9 0
1 2
1 3
2 3

예제 출력 1

1
1
1

예제 입력 2

2 1
1 1 2 2
3 3 4 4
1 2

예제 출력 2

0

출처

Camp > ICPC Sinchon Algorithm Camp > 2021 ICPC Sinchon Winter Algorithm Camp Contest - 중급 D번