예약 기록 캐시

문제

병원 예약 시스템은 환자 번호로 예약 기록을 조회할 때 속도를 높이기 위해 메모리 캐시를 사용한다. 캐시에는 환자 기록을 최대 C개까지 보관할 수 있고, 각 기록에는 마지막으로 접근한 시각이 함께 저장된다. 조회 요청은 (시각 t, 환자 번호 id) 쌍으로 들어오며 시각이 작은 것부터 순서대로, 같은 시각이면 입력 순서대로 처리한다. 처리 규칙은 다음과 같다. 첫째, 캐시에 id 가 있고 t − (저장된 마지막 접근 시각) ≤ T 이면 적중이다. 둘째, 캐시에 id 가 있지만 그 차이가 T 보다 크면 기록이 오래된 것이므로 적중이 아니라 실패로 센다. 이때 기록은 다시 불러와 캐시에 그대로 남기며 개수는 변하지 않는다. 셋째, 캐시에 id 가 없으면 실패이며 새 기록을 넣는다. 넣은 뒤 보관 개수가 C 를 넘으면 가장 오래전에 접근한 기록 하나를 쫓아내고 쫓아낸 횟수를 1 늘린다. 적중이든 실패든 id 의 마지막 접근 시각은 t 로 갱신되고 가장 최근에 접근한 기록이 된다. 모든 요청을 처리한 뒤 적중 횟수, 실패 횟수, 쫓아낸 횟수와 캐시에 남은 환자 번호를 가장 최근에 접근한 것부터 순서대로 구하는 프로그램을 작성하라. 유효 기간이 지난 기록도 쫓겨나기 전까지는 캐시에 남아 있는 것으로 본다.

입력

첫 줄에 요청 수 Q, 캐시 크기 C, 유효 기간 T 가 공백으로 주어진다. (1 ≤ Q ≤ 200,000, 1 ≤ C ≤ 200,000, 0 ≤ T ≤ 10^9) 이어지는 Q개의 줄에 t 와 id 가 공백으로 주어진다. (0 ≤ t ≤ 10^9, 1 ≤ id ≤ 10^9, 정수) t 는 줄 순서대로 감소하지 않는다.

출력

첫 줄에 적중 횟수, 실패 횟수, 쫓아낸 횟수를 공백으로 구분해 출력한다. 둘째 줄에 캐시에 남은 환자 번호를 가장 최근에 접근한 것부터 공백으로 구분해 출력한다. 요청이 1개 이상이므로 캐시는 비지 않는다.

6 2 10
0 1
5 2
8 1
20 2
21 3
22 1

1 5 2
1 3

3 1 0
4 7
4 7
5 7

1 2 0
7

출처: Devin.KR 자체 제작