Milk Measurement

题目描述

农夫约翰的每头奶牛起初每天产奶 $G$ 加仑（$1 \leq G \leq 10^9$）。由于奶牛的产奶量可能会随时间变化，农夫约翰决定定期测量产奶量，并将结果记录在日志中。日志条目形如： 35 1234 -2 14 2345 +3 第一条表示在第 35 天，编号为 1234 的奶牛的产奶量比上一次测量时减少了 2 加仑。下一条表示在第 14 天，编号为 2345 的奶牛的产奶量比上一次测量时增加了 3 加仑。 农夫约翰每天最多只能进行一次测量。不幸的是，他有点不够有条理，并不一定按时间顺序记录测量结果。 为了激励奶牛，农夫约翰会在谷仓墙上展示当前产奶量最高的奶牛的照片（如果有多头奶牛并列最高，则展示所有并列最高者的照片）。请确定农夫约翰需要更换这面展示的天数。 注意：农夫约翰的牛群非常庞大，因此尽管日志中记录了一些奶牛的产奶量发生变化，但总会有大量其他奶牛的产奶量始终保持为 $G$ 加仑。

输入格式

输入第一行包含测量次数 $N$（$1 \leq N \leq 100,000$），以及 $G$。接下来的 $N$ 行每行包含一次测量，格式如上：给出某一天（整数范围 $1 \ldots 10^6$）、一头奶牛的整数 ID（范围 $1 \ldots 10^9$），以及自上次测量以来该奶牛产奶量的变化值（一个非零整数）。每头奶牛的产奶量始终在范围 $0 \ldots 10^9$ 内。

输出格式

请输出农夫约翰需要调整其激励展示的天数。

4 10
7 3 +3
4 2 -1
9 3 -1
1 1 +2

3

提示

题目作者：Brian Dean

标签: USACO|2017|Silver

来源

USACO|2017|Silver