#F2. 食堂排队

食堂排队

T2 食堂排队(queue)

时间限制:1.0 秒 空间限制:256 MB

题目描述

学校食堂只有一个打饭窗口,窗口在时刻 00 时空闲。共有 nn 名同学要打饭,按到达先后顺序编号为 1,2,…,n1, 2, \dots, n。第 ii 名同学在时刻 tit_i 到达,打饭需要 cic_i 秒,耐心值为 wiw_i。

窗口一次只能为一名同学打饭,打饭过程不能被打断。同学按编号顺序依次排队:当轮到第 ii 名同学时(即编号比他小的同学都已经打完饭或离开),设此时窗口空闲的时刻为 TT,则他的开始打饭时刻为 S=max⁡(T,ti)S = \max(T, t_i),他的等待时间为 S−tiS - t_i。

  • 若等待时间严格大于 wiw_i,该同学会抱怨几句然后直接离开,不打饭(窗口空闲时刻 TT 保持不变);
  • 否则,该同学立即开始打饭,在时刻 S+ciS + c_i 打完饭离开,窗口空闲时刻变为 S+ciS + c_i。

保证 t1≤t2≤⋯≤tnt_1 \le t_2 \le \dots \le t_n(同时刻到达的同学按输入顺序排队)。

请你统计:

  1. 最终吃到饭的同学人数;
  2. 最后一名吃到饭的同学打完饭的时刻;
  3. 吃到饭的同学中最大的等待时间(若没有人吃到饭,则后两项均输出 00)。

注意:离开的同学的等待时间不计入第 3 项。

输入格式

第一行一个正整数 nn。

接下来 nn 行,每行三个非负整数 ti,ci,wit_i, c_i, w_i,含义如题述。

输出格式

输出一行,包含三个整数,用一个空格分隔:吃到饭的人数、最后结束时刻、吃到饭的同学中的最大等待时间。

样例 1

输入:

5
1 3 0
2 4 10
4 2 0
10 1 100
11 5 0

输出:

4 16 2

样例 1 解释: 同学 1 在时刻 1 开始打饭(等待 0),时刻 4 结束;同学 2 在时刻 4 开始(等待 2),时刻 8 结束;轮到同学 3 时窗口空闲时刻为 8,等待 8−4=4>08 - 4 = 4 > 0,他离开;同学 4 在时刻 10 开始,时刻 11 结束;同学 5 在时刻 11 开始,时刻 16 结束。因此吃到饭 4 人,最后结束时刻 16,最大等待时间为 2。

样例 2

输入:

4
1 5 0
3 2 1
4 1 10
5 1 0

输出:

2 7 2

样例 2 解释: 同学 1 在时刻 1 开始,时刻 6 结束;同学 2 等待 6−3=3>16 - 3 = 3 > 1,离开;同学 3 等待 6−4=2≤106 - 4 = 2 \le 10,在时刻 6 开始,时刻 7 结束;同学 4 等待 7−5=2>07 - 5 = 2 > 0,离开。

数据范围

对于全部测试数据:1≤n≤1051 \le n \le 10^5;1≤ti≤1091 \le t_i \le 10^9;1≤ci≤1051 \le c_i \le 10^5;0≤wi≤10100 \le w_i \le 10^{10};保证 tit_i 非递减。

注意: 最后结束时刻可能很大(超过 32 位整数的表示范围),请使用 64 位整数。