20561번 - 과제 해결하기 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2.5 초 | 1024 MB | 124 | 35 | 17 | 31.481% |
문제
오늘 송죽학사에 $N$개의 과제가 올라올 예정이다. 종영이와 친구들은 그다지 과제를 하고 싶지 않으므로 과제들을 분담해서 해결하기로 했다.
과제 $i$는 시각 $L_i$에 올라와 시각 $R_i$까지 제출할 수 있는데, 학생들의 학습능력이 그다지 뛰어나지 않아 제출이 가능한 시간 내내 그 과제를 해결해야 한다. 또 한 학생이 동시에 두 과제를 해결할 수 없으므로 두 과제 $i$와 $j$를 한 학생이 해결하려면 $R_i < L_j$ 또는 $R_j < L_i$를 만족해야 한다. 또 학생들은 과제에 그다지 큰 관심이 없으므로 한 학생당 최대 두 개의 과제를 해결할 것이다.
$M$명의 학생이 최대한 많은 과제를 해결하고자 할 때, 학생들 각각이 해결해야 할 과제를 정해주자. 가능한 경우가 여럿 있을 경우 어떤 방법을 선택하여도 좋다.
입력
첫 줄에 정수 $N$과 $M$이 주어진다. $(1 \leq M \leq N \leq 300\,000)$
이후 $N$개의 줄에 걸쳐 정수 $L_i$와 $R_i$가 주어진다. $(1 \leq L_i < R_i \leq 10^9)$
출력
$N$개의 수를 공백으로 구분하여 출력한다. $i$번째 수로는 과제 $i$를 해결할 학생을 출력한다. 과제 $i$를 해결할 학생이 없다면 대신 0을 출력한다.
예제 입력 1
7 5 9 10 7 9 3 4 9 10 2 6 8 9 5 8
예제 출력 1
3 2 2 5 5 4 1
예제 입력 2
2 2 1 2 3 4
예제 출력 2
1 1
예제 입력 3
2 1 1 2 2 3
예제 출력 3
1 0
출처
High School > 경기과학고등학교 > 나는코더다 2020 송년대회 J번
Camp > Petrozavodsk Programming Camp > Winter 2021 > Day 9: Grand Prix of Suwon K번
Contest > Open Cup > 2020/2021 Season > Stage 13: Grand Prix of Suwon K번
- 문제를 검수한 사람: cs71107, kdh9949, yclock
- 문제를 만든 사람: moonrabbit2
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호