시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 151 | 73 | 63 | 55.263% |
영대는 작은 공장을 운영하고 있다. 오늘로 영대는 공장을 운영한 지 $K$ 일($ 1 \le K \le 10^6 $)째가 되었다.
영대의 공장에서는 총 $N$($ 1 \le N \le 3 \cdot 10^5 $) 명의 직원이 일을 했다.
이 공장의 일은 매일매일 일을 하며 숙련도가 좋아질 수록 더 많은 수익을 낸다. 각 직원은 근무를 시작한 지 $i$일째에 $i$원 만큼의 수익을 영대에게 가져다 준다.
영대는 매일 자신이 얼만큼 수익을 벌었는지를 장부에 기록해두었지만, 잠깐 외출한 사이 배가 고팠던 그의 반려견 별이가 장부를 모두 먹어치워 버렸다. 영대는 화가 났지만 개가 뭘 알겠는가.. 어쩔 수 없이 영대는 당신에게 도움을 요청했다. 다행히도 각 직원의 작업 일지가 남아 있었기 때문에 작업 일지를 기반으로 장부를 복구할 수 있다. 작업 일지에는 각각의 $i$ 번째 직원에 대해 $i$번째 직원이 일을 시작한 날짜 $S_i$와 일을 그만둔 날짜(마지막으로 일한 날짜) $E_i$가 기록되어 있다($ 1 \le S_i \le E_i \le K $).
영대를 도와 이 기록을 바탕으로 장부를 복구해 보자.
첫째 줄에 영대의 공장에서 일한 직원의 수 $N$ 과 영대가 공장을 운영한 날짜 $K$가 주어진다($ 1 \le N \le 3 \cdot 10^5, 1 \le K \le 10^6 $).
둘째 줄부터 $N$줄에 걸쳐 영대의 직원이 일을 한 기간 $S_i, E_i$가 공백으로 구분되어 주어진다($ 1 \le S_i \le E_i \le K $, $S_i, E_i$는 정수). 이는 $i$ 번째 직원이 $S_i$ 일부터 $E_i$ 일까지 영대의 공장에서 일을 했다는 뜻이다.
첫째 줄에 $K$개의 수를 공백으로 구분하여 출력한다. $i$번째로 출력되는 수는 영대가 $i$번째 날에 벌어들인 수익의 양과 같아야 한다.
3 7 1 3 4 6 2 5
1 3 5 4 6 3 0
각 직원이 벌어들인 수익은 다음과 같다.
따라서 각 날짜 별로 직원들이 벌어들인 수익을 합치면 주어진 출력과 일치하게 된다.