헬스장 출입 로그 집계

문제

백엔드 운영 담당자인 당신은 헬스장 출입 단말기가 하루 동안 남긴 로그를 집계해야 한다. 로그는 한 줄에 'HH:MM 이벤트 회원번호' 형식이며, 이벤트는 IN(입장) 또는 OUT(퇴장)이다. 로그는 시각이 같거나 늦어지는 순서로 기록되어 있고, 시각이 같은 로그는 주어진 순서대로 처리한다. 단말기 오류로 비정상 로그가 섞여 있다. 이미 안에 있는 회원의 IN, 그리고 안에 있지 않은 회원의 OUT은 비정상 로그이며 집계에서 완전히 무시한다. 나머지는 정상 로그이다. 하루가 끝나는 24:00(= 1440분)에 아직 안에 있는 회원은 그 시각에 퇴장한 것으로 본다. 시각은 자정 이후 경과한 분으로 환산한다. 다음 네 가지를 출력한다. (1) 비정상 로그의 수. (2) 현재 인원이 정원 C보다 많았던 총 시간(분). 연속한 정상 로그 사이의 구간과 마지막 정상 로그부터 1440분까지의 구간에서, 그 구간 동안 유지된 인원이 C보다 크면 구간 길이를 더한다. 첫 정상 로그 이전의 인원은 0이다. (3) 하루 동안 머문 시간의 합이 가장 긴 회원의 번호와 그 합(분). 정상 IN이 한 번이라도 있었던 회원만 대상이며 합이 같으면 번호가 작은 회원을 고른다. 대상 회원이 없으면 NONE을 출력한다. (4) 정상 로그 직후의 인원 중 최댓값과 그 값이 처음 나타난 시각(HH:MM). 정상 로그가 없으면 '0 00:00'을 출력한다.

입력

첫 줄에 로그의 수 N과 정원 C가 주어진다. 이어지는 N개의 줄에 각각 'HH:MM 이벤트 회원번호'가 주어진다. 1 ≤ N ≤ 200,000, 0 ≤ C ≤ 200,000, 00:00 ≤ 시각 ≤ 23:59(두 자리 0 채움), 이벤트는 IN 또는 OUT, 1 ≤ 회원번호 ≤ 100,000 이다. 시각은 비내림차순이다.

출력

네 줄을 출력한다. 첫 줄에 비정상 로그의 수, 둘째 줄에 정원 초과 총 시간(분), 셋째 줄에 '회원번호 머문 시간' 또는 NONE, 넷째 줄에 '최대 인원 HH:MM'을 출력한다.

8 1
09:00 IN 5
09:10 IN 7
09:20 OUT 5
09:30 OUT 9
09:40 IN 7
10:00 OUT 7
10:05 IN 5
10:05 OUT 5

2
10
7 50
2 09:10

3 0
23:00 IN 1
23:30 IN 2
23:59 OUT 1

0
60
1 59
2 23:30

2 5
00:00 OUT 3
00:00 OUT 3

2
0
NONE
0 00:00

출처: Devin.KR 자체 제작