A 工厂新引进了一批机器,这批机器每台每天可以生产 P 个零件。为保障机器能够稳定运行,公司为这批机器专门聘请了张师傅和他的徒弟孙师傅来维护这批机器。
每天张师傅最多会选择 1 台机器进行维护(也可能当天张师傅休息,因此当天没有维护机器)。如果机器运行情况特别好,张师傅会在维护之后将该机器的单日零件产量提高一些。如果机器磨损严重,张师傅会在维护之后将该机器的单日零件产量降低一些,以保证机器的稳定运行。
只要有机器单日的零件产量发生了变化,张师傅的徒弟孙师傅就会记录下来。比如:下面是孙师傅最近的工作记录。
5 2 +8
2 1 -2
3 8 +9
这份工作记录有若干行,第 i 行有 3 个整数 T_i,X_i,C_i,分别表示,在这批机器投入生产后的第 T_i 天,编号为 X_i 的机器,该机器在维护之后,其单日零件产量相比较维护之前,变化了 C_i 个。
比如,上面记录的第 1 行记录了,在第 5 天,2 号机的单日零件产量在维护后,相比较维护前,增加了 8 个。值得注意的是通过这份维修记录,我们可以看到孙师傅并不是严格按照时间顺序做工作记录。
工厂要求,只要当天单日零件产量最多的机器发生了变化(比如单日零件产量最多的机器数量变化了,或者编号发生了变化),那么当天一定通过电子邮件向工厂提交这一天的工作记录。
请编程计算出,根据孙师傅的工作记录,一共要通过电子邮件向工厂提交多少份工作记录。
第 1 行有两个整数 N,P ,表示孙师傅的工作记录一共有 N 行,所有机器刚引进时,单日的零件产量为 P 个。
接下来 N 行,每行有 3 个整数 T_i,X_i,C_i ,含义如题所述。
输出一个整数,代表需要提交工作记录的份数。
5 20 1 5 +3 2 3 -1 5 5 -1 6 2 +2 10 5 -2
3
8 100 3 5 -10 8 8 +20 9 8 +30 20 10 +30 1 3 -10 12 6 +50 30 5 +50 25 10 +20
5
4 10 7 3 +3 4 2 -1 9 3 -1 1 1 +2
3
机器刚引进时,单日零件产量都为 20 个,可以认为此时所有机器的单日零件产量都是最高的。
第 1 天,5 号机的单日零件产量提升了 3 个,5 号机产量最高,需要提交工作记录。
第 2 天,2 号机的单日零件产量降低了 1 个,依然是 5 号机产量最高,不需要提交工作记录。
第 5 天,5 号机的单日零件产量降低了 1 个,依然是 5 号机产量最高,不需要提交工作记录。
第 6 天,6 号机的单日零件产量增加了 2 个,5 号机和 6 号机的产量并列最高,需要提交工作记录。
第 10 天,5 号机的单日零件产量降低了 2 个,6 号机的产量最高,需要提交工作记录。
因此一共需要提交 3 份工作记录。
1 \le N \le 10^5,1 \le P \le 10^9,1 \le T_i \le 10^6,1 \le X_i \le 10^9,1 \le | C_i | \le 10^6。(|C_i| 表示求 C_i 的绝对值)
请注意,无论机器的单日产量增加还是减少,其零件单日产量的值都一定维持在 [0,10^9] 的范围内。
东方博宜OJ