자전거 운행 기록 정제

문제

공유 자전거 운영팀은 단말기에서 모은 운행 기록을 일일 점검 자료로 만들고 있다. 통신이 불안정한 단말기는 잘못된 시간을 보내거나 같은 자전거의 기록을 여러 번 보낼 수 있다. 데이터 담당자는 정해진 검증 규칙을 적용한 뒤, 자전거마다 대표 기록 하나를 골라 점검 자료를 만들기로 했다. 각 기록에는 자전거 번호, 출발 시각, 도착 시각, 이동 거리가 들어 있다. 두 시각은 점검 기간의 기준 시점부터 지난 분을 나타내는 정수이며, 이동 거리는 미터 단위의 정수이다. 입력된 순서는 서버가 기록을 받은 순서이다. 기록이 늦게 도착할 수 있으므로 입력 순서가 운행 시각의 순서와 같다고 가정할 수 없다. 먼저 각 기록을 독립적으로 검증한다. 도착 시각이 출발 시각보다 반드시 커야 한다. 또한 이동 거리가 운행 시간에 500을 곱한 값 이하여야 한다. 여기서 운행 시간은 도착 시각에서 출발 시각을 뺀 값이다. 두 조건 중 하나라도 만족하지 못하면 잘못된 기록으로 분류하고, 대표 기록을 고르는 과정에서는 완전히 제외한다. 이동 거리가 0인 기록도 두 조건을 만족하면 유효하다. 다음으로 유효한 기록만 사용하여 자전거마다 대표 기록을 하나씩 고른다. 같은 자전거의 유효한 기록 중 도착 시각이 가장 큰 기록을 고른다. 도착 시각이 같다면 입력에서 더 나중에 나온 기록을 고른다. 출발 시각이나 이동 거리는 이 동점 처리에 사용하지 않는다. 잘못된 기록이 나중에 등장하더라도 이미 확인한 유효한 기록을 취소하지 않는다. 최종 점검 자료에는 유효한 기록이 하나 이상 있는 자전거만 포함된다. 잘못된 기록의 개수, 점검 자료에 포함된 자전거의 수, 선택된 대표 기록들의 이동 거리 합을 구한다. 대표 기록으로 선택되지 않은 유효한 기록은 잘못된 기록의 개수에 포함하지 않는다. 유효한 기록이 전혀 없으면 자전거 수와 이동 거리 합은 모두 0이다.

입력

첫째 줄에 기록 수를 나타내는 정수 N이 주어진다. 1≤N≤10,000이다.
다음 N개 줄에 자전거 번호 I, 출발 시각 S, 도착 시각 E, 이동 거리 D가 공백으로 구분되어 주어진다. 모두 정수이며 1≤I≤10,000, 0≤S,E≤1,000,000, 0≤D≤100,000이다.

출력

잘못된 기록의 개수, 대표 기록이 선택된 자전거의 수, 대표 기록들의 이동 거리 합을 공백으로 구분하여 한 줄에 출력한다.

6
1 0 2 900
1 1 3 1000
2 5 5 0
2 4 6 1200
3 8 10 500
1 2 3 400

2 2 900

3
7 4 4 0
8 9 8 1
7 0 1 501

3 0 0

3
4 2 4 100
4 0 3 200
9 5 6 0

0 2 100

출처: Devin.KR 자체 제작