#F2. 食堂排队
食堂排队
T2 食堂排队(queue)
时间限制:1.0 秒 空间限制:256 MB
题目描述
学校食堂只有一个打饭窗口,窗口在时刻 时空闲。共有 名同学要打饭,按到达先后顺序编号为 。第 名同学在时刻 到达,打饭需要 秒,耐心值为 。
窗口一次只能为一名同学打饭,打饭过程不能被打断。同学按编号顺序依次排队:当轮到第 名同学时(即编号比他小的同学都已经打完饭或离开),设此时窗口空闲的时刻为 ,则他的开始打饭时刻为 ,他的等待时间为 。
- 若等待时间严格大于 ,该同学会抱怨几句然后直接离开,不打饭(窗口空闲时刻 保持不变);
- 否则,该同学立即开始打饭,在时刻 打完饭离开,窗口空闲时刻变为 。
保证 (同时刻到达的同学按输入顺序排队)。
请你统计:
- 最终吃到饭的同学人数;
- 最后一名吃到饭的同学打完饭的时刻;
- 吃到饭的同学中最大的等待时间(若没有人吃到饭,则后两项均输出 )。
注意:离开的同学的等待时间不计入第 3 项。
输入格式
第一行一个正整数 。
接下来 行,每行三个非负整数 ,含义如题述。
输出格式
输出一行,包含三个整数,用一个空格分隔:吃到饭的人数、最后结束时刻、吃到饭的同学中的最大等待时间。
样例 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,等待 ,他离开;同学 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 等待 ,离开;同学 3 等待 ,在时刻 6 开始,时刻 7 结束;同学 4 等待 ,离开。
数据范围
对于全部测试数据:;;;;保证 非递减。
注意: 最后结束时刻可能很大(超过 32 位整数的表示范围),请使用 64 位整数。