보급
다이아몬드 V의견: 0
2차원 평면에 N개의 군사 기지가 있는 구역이 있다. 각 i번째 부대의 위치는 좌표 (Xi, Yi)로 알려져 있다. 이 구역을 담당한 보급 부대는 모든 기지에 보급을 수행하려고 한다. 각 i번째 기지가 보급을 받을 수 있는 날짜는 Ai번째부터 Bi번째 날짜까지이다. 전쟁 중이라, 보급 부대는 병력이 전체적으로 왼쪽 위에서 오른쪽 아래로 내려가는 모양의 대열을 유지하면서 오른쪽 위 방향으로 전진해야 한다. 따라서, 아래 조건들이 모두 만족되도록 각 i번째 기지가 보급을 받을 날짜 Vi를 하루씩 지정해야 한다.
- 모든 i에 대해 Ai ≤ Vi ≤ Bi이다.
- 모든 i, j에 대해 Xi < Xj, Yi < Yj 인 경우 Vi < Vj라야 한다.
- 모든 i, j에 대해 i ≠ j 이면 Vi ≠ Vj라야 한다.
각 기지의 위치와 보급 받을 수 있는 날짜들의 범위를 입력으로 받아 조건을 만족하면서 모든 기지에 보급을 할 수 있는지 확인하는 프로그램을 작성하라.
아래 예는 6개의 기지가 있는 상황을 보여 준다. 각 점이 기지에 해당하며 점 오른쪽 위에 보급을 받을 수 있는 날짜 범위가 주어져 있다.
아래 그림은 위의 예에서 조건을 만족하도록 보급 날짜를 정한 예를 보여준다. 각 점 오른쪽 아래에 배정된 날짜가 표기되어 있다. 아래 그림의 곡선은 보급 부대의 대형이 2일째와 3일째 사이에 있을 수 있는 가능한 위치를 보여 준다.
- 주어지는 모든 수는 정수이다.
- \(1 \le N \le 250\,000\)
- \(1 \le A_i \le B_i \le N\)
- \(1 \le X_i \le N\)
- \(1 \le Y_i \le N\)
- 모든 \(X_i\)는 서로 다르다. 즉 \(i \ne j\)이면 \(X_i \ne X_j\)이다.
- 모든 \(Y_i\)는 서로 다르다. 즉 \(i \ne j\)이면 \(Y_i \ne Y_j\)이다.
첫 번째 줄에 기지의 개수 N이 주어진다.
다음 N개의 줄 중 i번째 줄에 기지의 정보 Xi, Yi, Ai, Bi가 공백을 사이에 두고 주어진다.
보급 날짜 배정이 가능한 경우 첫 번째 줄에 YES를 출력한다. 다음 줄에 기지 번호 순서대로 배정된 날짜 들을 공백을 사이에 두고 출력한다.
보급 날짜 배정이 불가능한 경우 첫 번째 줄에 NO를 출력한다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 13점 | \(N \le 10\). |
2 | 18점 | \(N \le 2\,500\). |
3 | 22점 | 모든 \(i\)에 대해 \(B_i = N\)이다. |
4 | 47점 | 추가 제약 조건 없음. |
6
2 6 1 3
4 1 4 6
6 5 4 6
1 3 2 5
3 2 1 3
5 4 1 6
YES
3 4 6 2 1 5
2
1 1 2 2
2 2 1 1
NO
riseoj 작성
출처 올림피아드 > 한국정보올림피아드 > KOI 2022 > 1차 대회 > 고등부 3번
평가 및 의견
보급
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
보급