음악 축제 무대 중복
골드 IV의견: 0
여름 음악 축제 '리세 사운드'에는 \(N\)개의 무대가 각각 시간 \(L_i\)에 시작해 시간 \(R_i\)에 끝난다 (반열린 구간 \([L_i, R_i)\)). 관람객은 여러 무대를 동시에 볼 수는 없지만, 운영진은 두 가지 통계를 내려고 한다.
- 동시에 진행 중인 무대 수의 최댓값 \(P\)
- 동시에 \(K\)개 이상의 무대가 진행되는 시간 구간의 총 길이 \(C\)
두 값을 구하여라.
- \(1 \le K \le N \le 200\,000\)
- \(-10^9 \le L_i < R_i \le 10^9\)
- 정수 좌표이다.
첫째 줄에 무대 수 \(N\)과 기준 값 \(K\)가 공백으로 구분되어 주어진다.
다음 \(N\)개의 줄에 각 무대의 시작 시각 \(L_i\)와 종료 시각 \(R_i\)가 공백으로 구분되어 주어진다.
첫째 줄에 동시에 진행 중인 무대 수의 최댓값 \(P\)를 출력한다.
둘째 줄에 동시에 \(K\)개 이상의 무대가 진행되는 시간의 총 길이 \(C\)를 출력한다.
4 2
1 5
2 8
4 7
9 11
3
5
동시에 진행되는 최대 무대 수는 \([4,5)\) 구간에서 \(3\)개이다. \(K=2\) 이상이 겹치는 총 구간 길이는 \([2,5)\)와 \([4,7)\)이 합쳐진 \([2,7) = 5\)이다.
3 3
0 10
0 10
0 10
3
10
세 무대 모두 \([0,10)\) 전체에서 겹친다. 최대 동시 무대 수는 \(3\)이고, \(K=3\) 이상 겹치는 구간 길이도 \(10\)이다.
riseoj 작성
출처 Original
평가 및 의견
음악 축제 무대 중복
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
음악 축제 무대 중복