레이팅 미적용\(1\)번부터 \(N\)번까지 번호가 매겨진 \(N\)개의 칸이 일렬로 놓여 있다. 두 곡예사 앨리스(Alice)와 밥(Bob)이 이 칸들 위에서 공연을 한다. 매 순간 두 곡예사는 각각 정확히 한 칸 위에 서 있으며, 항상 앨리스가 서 있는 칸의 번호가 밥이 서 있는 칸의 번호보다 반드시 작아야 한다.
무대에는 \(M\)개의 점프대가 있다. \(i\)번 점프대는 \(x_i\)번 칸 위에 설치되어 있으며, \(x_i\)번 칸 위에 서 있는 곡예사를 \(y_i\)번 칸으로 보낸다 (\(x_i \neq y_i\)). 하나의 칸에 여러 개의 점프대가 설치되어 있을 수도 있다. 두 곡예사 모두 어떤 점프대든 원하는 만큼 여러 번 사용할 수 있다.
공연은 \(0\)개 이상의 행동으로 이루어진 수열이다. 각 행동에서는 두 곡예사 중 정확히 한 명이 다음 중 하나를 수행한다.
걷기(Walk)
- 앨리스가 행동하는 경우: 앨리스는 자신이 서 있는 칸에서 번호가 \(1\) 큰 칸(오른쪽)으로 이동한다. 앨리스는 오른쪽으로만 걸을 수 있다.
- 밥이 행동하는 경우: 밥은 자신이 서 있는 칸에서 번호가 \(1\) 작은 칸(왼쪽)으로 이동한다. 밥은 왼쪽으로만 걸을 수 있다.
점프(Jump)
- \(x_i\)번 칸 위에 서 있는 곡예사가 \(i\)번 점프대를 사용하여 \(y_i\)번 칸으로 이동한다.
단, 어떤 행동을 수행한 직후에도 앨리스가 서 있는 칸의 번호가 밥이 서 있는 칸의 번호보다 반드시 작아야 한다. 이 조건을 위반하게 되는 행동은 수행할 수 없다.
\(Q\)개의 질문이 주어진다. 각 질문은 네 정수 \(a, b, c, d\) (\(a < b\), \(c < d\))로 이루어진다. 처음에 앨리스가 \(a\)번 칸, 밥이 \(b\)번 칸에 서 있는 상태에서 공연을 시작하여, 앨리스가 \(c\)번 칸, 밥이 \(d\)번 칸에 서 있는 상태로 공연을 마칠 수 있는지 판정하라.
- 주어지는 모든 수는 정수이다.
- \(2 \le N \le 200\,000\)
- \(0 \le M \le 200\,000\)
- \(1 \le Q \le 500\,000\)
- 모든 \(i\) \((1 \le i \le M)\)에 대하여 \(1 \le x_i, y_i \le N\)이고 \(x_i \neq y_i\)이다.
- 모든 질문 \((a, b, c, d)\)에 대하여 \(1 \le a < b \le N\)이고 \(1 \le c < d \le N\)이다.
첫 줄에 두 정수 \(N\)과 \(M\)이 공백으로 구분되어 차례대로 주어진다.
이어지는 \(M\)개의 줄 중 \(i\)번째 줄에는 \(i\)번 점프대의 정보를 나타내는 두 정수 \(x_i\)와 \(y_i\)가 공백으로 구분되어 주어진다.
그다음 줄에 질문의 개수 \(Q\)가 주어진다.
이어지는 \(Q\)개의 줄 중 \(j\)번째 줄에는 \(j\)번째 질문을 나타내는 네 정수 \(a, b, c, d\)가 공백으로 구분되어 주어진다.
각 질문에 대하여, 가능하면 YES를, 불가능하면 NO를 한 줄에 하나씩, 질문이 주어진 순서대로 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 8점 | \(N, M, Q \le 100\) |
Subtask 2 | 14점 | 모든 \(i\)에 대하여 \(x_i < y_i\)이다. |
Subtask 3 | 13점 | \(N \le 3\,000\) |
Subtask 4 | 13점 | \(Q \le 10\) |
Subtask 5 | 52점 | 추가적인 제약 조건이 없다. |
6 2
3 5
4 2
4
2 4 3 4
2 3 2 5
2 3 4 5
3 4 1 2
YES
YES
YES
NO
생성자가 기록되지 않았습니다.
출처 올림피아드 > 한국정보올림피아드 > KOI 2026 > 2차 대회 > 고등부