레이팅 미적용농부 존의 소들은 처음에 각각 하루에 \(G\)갤런의 우유를 생산한다 (\(1 \leq G \leq 10^9\)). 소의 우유 생산량은 시간이 지나면서 바뀔 수 있다고 알려져 있으므로, 농부 존은 주기적으로 우유 생산량을 측정하고 그 결과를 기록장에 적어 두기로 했다. 기록장의 항목은 다음과 같은 형태이다.
35 1234 -2
14 2345 +3
첫 번째 항목은 35일째에 1234번 소의 우유 생산량이 마지막으로 측정했을 때보다 2갤런 줄었다는 의미이다. 다음 항목은 14일째에 2345번 소의 우유 생산량이 마지막으로 측정했을 때보다 3갤런 늘었다는 의미이다. 농부 존은 하루에 최대 한 번의 측정만 할 시간이 있다. 안타깝게도 그는 다소 정리가 서툴러서, 측정 기록을 반드시 시간 순서대로 적지는 않는다.
소들에게 동기를 부여하기 위해, 농부 존은 현재 우유 생산량이 가장 많은 소의 사진을 헛간 벽에 자랑스럽게 걸어 둔다 (여러 소가 최고 생산량으로 동률이면 그 소들의 사진을 모두 건다). 농부 존이 이 게시물을 바꿔야 했을 날이 며칠인지 구하라.
농부 존의 소 떼는 매우 크기 때문에, 기록장에 우유 생산량이 변했다고 적힌 소들이 있더라도, 우유 생산량이 \(G\)갤런으로 유지되는 다른 소들이 항상 충분히 많이 있다는 점에 유의한다.
Problem credits: Brian Dean
Problem credits: Brian Dean
입력의 첫째 줄에 농부 존이 수행한 측정의 횟수 \(N\) (\(1 \leq N \leq 100,000\))과 \(G\)가 주어진다. 다음 \(N\)개의 줄에 위 형식대로 측정 기록이 하나씩 주어지며, 각 기록은 날짜 (\(1 \ldots 10^6\) 범위의 정수), 소의 정수 ID (\(1 \ldots 10^9\) 범위), 그리고 마지막 측정 이후 우유 생산량의 변화량 (0이 아닌 정수)으로 이루어져 있다. 각 소의 우유 생산량은 항상 \(0 \ldots 10^9\) 범위이다.
농부 존이 동기 부여 게시물을 바꿔야 하는 날의 수를 출력한다.
measurement.in · 출력을 쓸 파일 measurement.out4 10
7 3 +3
4 2 -1
9 3 -1
1 1 +23riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > December > Silver