게임 점수 스냅샷 정제

문제

게임 서버의 데이터 담당자는 하루 동안 수집한 점수 스냅샷을 정제하여 운영 화면에 사용할 요약을 만들려고 한다. 입력에는 수집 순서대로 N개의 기록이 들어 있다. 각 기록은 이용자 번호 U, 점수 S, 검증 표시 F로 구성된다. 같은 이용자의 기록이 여러 번 들어올 수 있으며, 뒤에 나오는 기록일수록 나중에 수집된 기록이다. 별도의 시각 정보는 없고 입력 순서만 사용한다. 기록이 유효하려면 검증 표시 F가 1이고 점수 S가 0 이상 100,000 이하여야 한다. 두 조건을 모두 만족해야 하며, 하나라도 만족하지 않으면 무효 기록이다. 이용자 번호는 입력 단계에서 이미 확인되었으므로 번호에 대한 추가 검증은 하지 않는다. 점수가 허용 범위를 벗어나면 경계값으로 고치지 않고 기록 전체를 무효로 처리한다. 정제 결과에는 이용자마다 가장 나중에 수집된 유효 기록 하나만 남긴다. 어떤 이용자의 첫 유효 기록을 만나면 그 기록을 새로 보관한다. 이미 유효 기록을 보관한 이용자의 유효 기록을 다시 만나면 기존 기록을 새 기록으로 교체하고 교체 횟수를 하나 늘린다. 두 기록의 점수가 같아도 교체한 것으로 센다. 반면 무효 기록은 무효 횟수만 늘리고 즉시 버린다. 따라서 무효 기록이 더 나중에 등장해도 이전에 보관한 유효 기록을 지우거나 바꾸지 않는다. 모든 기록을 처리한 뒤에는 보관된 이용자 수, 버린 무효 기록 수, 유효 기록을 교체한 횟수를 집계한다. 이어서 보관된 최종 점수가 가장 높은 이용자를 운영 화면의 대표 이용자로 선택한다. 최고 점수가 같은 이용자가 여러 명이면 이용자 번호가 가장 작은 사람을 선택한다. 중간에 보관했던 점수는 대표 이용자를 고를 때 사용하지 않는다. 정제 요약과 대표 이용자의 번호 및 최종 점수를 구하는 프로그램을 작성한다. 유효 기록이 하나도 없으면 보관된 이용자가 없으며, 이 경우 대표 이용자도 없음을 정해진 형식으로 출력한다.

입력

첫째 줄에 기록 수 N이 주어진다.
다음 N개의 줄에 세 정수 U, S, F가 공백으로 구분되어 수집 순서대로 주어진다.
1 ≤ N ≤ 16,000, 1 ≤ U ≤ 99,999, -999 ≤ S ≤ 999,999, F ∈ {0, 1}이다.

출력

첫째 줄에 보관된 이용자 수, 무효 기록 수, 교체 횟수를 차례대로 공백으로 구분하여 출력한다. 둘째 줄에 대표 이용자의 번호와 최종 점수를 공백으로 구분하여 출력한다. 보관된 이용자가 없으면 둘째 줄에 -1 -1을 출력한다.

7
12 50 1
7 80 1
12 90 1
7 999999 1
3 90 1
12 20 0
3 90 1

3 2 2
3 90

3
1 -1 1
2 100001 1
3 0 0

0 3 0
-1 -1

4
9 100 1
9 20 1
4 20 1
9 0 1

2 0 2
4 20

출처: Devin.KR 자체 제작