루미 알고리즘

#1140다이아곡예곡예

KOI 2026 2차코딩고등부 3번출제 송준혁이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

곡예

원제: 곡예

문제

NN개의 칸이 일렬로 나열된 평균대 위에서 두 곡예사 Alice와 Bob이 공연을 진행하려고 한다. 평균대의 칸에는 왼쪽부터 오른쪽으로 11번부터 NN번까지의 번호가 붙어 있다.

공연을 진행하며 두 곡예사는 매 순간 정확히 하나의 칸 위에 서 있어야 한다. 또한 안전을 위해 공연 중 모든 순간에 대해 Alice가 서 있는 칸의 번호가 Bob이 서 있는 칸의 번호보다 작아야 한다. 즉, Alice는 항상 Bob보다 왼쪽 칸에 서 있어야 하며, 두 곡예사는 같은 칸에 서 있을 수 없다.

평균대에는 MM개의 점프대가 설치되어 있다. ii (1≤i≤M)(1 \le i \le M)번 점프대는 xix_i번 칸에 설치되어 있으며, xix_i번 칸에 서 있는 곡예사가 이 점프대를 이용하면 yiy_i번 칸에 정확히 착지한다.

한 칸에 여러 개의 점프대가 설치되어 있을 수도 있으며, 두 곡예사 모두 모든 점프대를 횟수 제한 없이 이용할 수 있다.

공연은 00번 이상의 행동을 차례로 수행하는 것으로 이루어진다. 한 번의 행동에서는 두 곡예사 중 정확히 한 명이 다음 두 가지 중 하나를 수행한다.

  1. 걷기: Alice는 자신이 서 있는 칸에서 오른쪽으로 한 칸 이동할 수 있고, Bob은 자신이 서 있는 칸에서 왼쪽으로 한 칸 이동할 수 있다. Alice가 왼쪽으로는 걸을 수 없으며, Bob도 오른쪽으로 걸을 수 없다.
  2. 점프: 자신이 서 있는 칸에 설치된 점프대 중 하나를 골라 점프한다. 즉, 어떤 정수 ii (1≤i≤M)(1 \le i \le M)에 대해 xix_i번 칸에 서 있는 곡예사는 ii번 점프대를 이용해 yiy_i번 칸으로 착지할 수 있다.

행동을 수행한 직후에도 Alice는 Bob보다 왼쪽 칸에 서 있어야 하며, 조건을 위반하게 되는 행동은 수행할 수 없다.

두 곡예사는 QQ개의 공연 계획을 가지고 있다. jj (1≤j≤Q)(1 \le j \le Q)번째 공연 계획은 1≤aj<bj≤N1 \le a_j < b_j \le N과 1≤cj<dj≤N1 \le c_j < d_j \le N을 만족하는 네 정수 aja_j, bjb_j, cjc_j, djd_j로 나타낼 수 있다. 만약 적절한 행동들을 통해 Alice가 aja_j번 칸, Bob이 bjb_j번 칸에 서 있는 상태로 공연을 시작하여, Alice가 cjc_j번 칸, Bob이 djd_j번 칸에 서 있는 상태로 공연을 마치는 것이 가능하다면, jj번째 공연 계획은 유효하다.

QQ개의 공연 계획에 대해서 각 계획이 유효한지 판정하라.

제약 조건

  • 주어지는 모든 수는 정수이다.
  • 2≤N≤200 0002 \le N \le 200\,000
  • 0≤M≤200 0000 \le M \le 200\,000
  • 1≤Q≤500 0001 \le Q \le 500\,000
  • 정수 ii (1≤i≤M)(1 \le i \le M)에 대하여, 1≤xi,yi≤N1 \le x_i, y_i \le N과 xi≠yix_i \ne y_i를 만족한다.
  • 정수 jj (1≤j≤Q)(1 \le j \le Q)에 대하여, 1≤aj<bj≤N1 \le a_j < b_j \le N과 1≤cj<dj≤N1 \le c_j < d_j \le N을 만족한다.

부분문제

  1. (8점) N,M,Q≤100N, M, Q \le 100
  2. (14점) 정수 ii (1≤i≤M)(1 \le i \le M)에 대하여 xi<yix_i < y_i
  3. (13점) N≤3 000N \le 3\,000
  4. (13점) Q≤10Q \le 10
  5. (52점) 추가 제약 조건 없음.

입력 형식

첫 줄에 두 정수 NN과 MM이 공백으로 구분되어 차례대로 주어진다.

그다음 MM개의 줄에 걸쳐, MM개의 점프대에 대한 정보가 주어진다. 이 중 ii (1≤i≤M)(1 \le i \le M)번째 줄에는 ii번째 점프대를 나타내는 두 정수 xix_i와 yiy_i가 공백으로 구분되어 차례대로 주어진다.

그다음 줄에 공연 계획의 개수를 나타내는 정수 QQ가 주어진다.

그다음 QQ개의 줄에 걸쳐, QQ개의 공연 계획에 대한 정보가 주어진다. 이 중 jj (1≤j≤Q)(1 \le j \le Q)번째 줄에는 jj번째 공연 계획을 나타내는 네 정수 aja_j, bjb_j, cjc_j, djd_j가 공백으로 구분되어 차례대로 주어진다.

출력 형식

첫 줄부터 QQ개의 줄에 걸쳐, 답을 출력한다. 이 중 jj (1≤j≤Q)(1 \le j \le Q)번째 줄에는 jj번째 공연 계획에 대한 답을 출력한다. 만약 Alice가 aja_j번 칸, Bob이 bjb_j번 칸에 서 있는 상태로 공연을 시작하여, Alice가 cjc_j번 칸, Bob이 djd_j번 칸에 서 있는 상태로 공연을 마칠 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.

예제

예제 1

입력
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

두 번째 공연 계획에서 Alice는 22번 칸, Bob은 33번 칸에서 공연을 시작한다. Bob이 33번 칸의 점프대를 이용해 55번 칸으로 이동하면 Alice가 22번 칸, Bob이 55번 칸에 서 있게 되어 목표에 도달한다.

네 번째 공연 계획에서 Alice가 33번 칸, Bob이 44번 칸에 서 있을 때는 어떤 행동도 할 수 없다.

  • Alice가 오른쪽으로 걸으면 두 곡예사가 모두 44번 칸에 서게 되어 조건을 위반한다.
  • Bob이 왼쪽으로 걸으면 두 곡예사가 모두 33번 칸에 서게 되어 조건을 위반한다.
  • Bob이 44번 칸의 점프대를 이용해 22번 칸에 착지하면, Bob이 33번 칸에 서 있는 Alice보다 왼쪽에 서게 되어 조건을 위반한다.

따라서, Alice가 11번 칸, Bob이 22번 칸에 서게 되는 목표 상태에 도달할 수 없다.

예제 2

입력
10 3
5 10
6 8
7 4
5
5 6 4 10
5 6 3 9
1 10 2 9
6 8 4 9
9 10 1 10
출력
YES
NO
YES
YES
NO

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2026년 2차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.