5843: YACS - 公交车站
[Creator : ]
Description
有一个公交车站,陆续有若干乘客前来排队,也陆续会有一些班车将乘客运走。
共有 $n$ 班公交车停靠该车站,对班车 $i$,有一个时间参数 $a_i$,表示它到达车站的时间,以及另外一个装载参数 $d_i$,表示这一班车能装载的乘客数量:
给定所有乘客以及所有班车的信息,请对于每一个乘客,输出他在车站等待上车的时长(单位为分钟),若该乘客放弃等待离开车站,则输出 Leave。
共有 $n$ 班公交车停靠该车站,对班车 $i$,有一个时间参数 $a_i$,表示它到达车站的时间,以及另外一个装载参数 $d_i$,表示这一班车能装载的乘客数量:
- 若排队人多,则优先载运到达时间靠前的乘客;
- 若排队人少,座位还有剩余,班车不会等待。
- 乘客 $j$ 的第一个参数表示他的到达时间 $s_j$;
- 第二个参数表示他的离开时间 $t_j$。太过漫长的等待会令人失去耐心。若他在时间 $t_j$ 前不能上车,乘客 $j$ 就会离开车站,选择其他交通方式。
- 若存在两位乘客的到达时间完全一致,则按输入时他们的序号顺序依次排队候车。例如:$2$ 号乘客和 $5$ 号乘客的到达时间相同,我们认为 $2$ 号乘客排在 $5$ 号乘客前面。
给定所有乘客以及所有班车的信息,请对于每一个乘客,输出他在车站等待上车的时长(单位为分钟),若该乘客放弃等待离开车站,则输出 Leave。
Input
第一行,两个正整数 $n$ 和 $m$;
接下来 $n$ 行,每行两个参数 $a_i,\ d_i$,表示第 $i$ 号班车的到达时间与最大载客数量。
接下来 $m$ 行,每行两个参数 $s_i,\ t_i$,表示第 $i$ 号乘客的到达时间与离开时间。
接下来 $n$ 行,每行两个参数 $a_i,\ d_i$,表示第 $i$ 号班车的到达时间与最大载客数量。
接下来 $m$ 行,每行两个参数 $s_i,\ t_i$,表示第 $i$ 号乘客的到达时间与离开时间。
Output
共 $m$ 行:表示 $m$ 个乘客的等待时间长度。
Constraints
- 对于 $30\%$ 的数据,$1 \leq n \leq 5,\ 1 \leq m \leq 10$
- 对于 $50\%$ 的数据,$1 \leq n \leq 100,\ 1 \leq m \leq 1000$
- 对于 $100\%$ 的数据,$1 \leq n \leq 1000,\ 1 \leq m \leq 10000$
Sample 1 Input
3 6
09:10 3
08:30 2
10:20 4
09:05 09:15
09:01 09:22
08:31 09:20
09:05 10:00
10:10 10:15
08:30 08:33
Sample 1 Output
5
9
39
Leave
Leave
0
1,2,3号乘客选乘09:10这班车,等待时间分别为5分钟、9分钟、39分钟。
4号乘客和1号乘客到达时间相同,排在1号乘客后面,因载客量未能乘09:10这班车,直到放弃时间没有公交车前来,则放弃乘坐
5号乘客直到放弃时间没有公交车前来,则放弃乘坐
6号乘客到站直接乘坐08:30这班车,等待时长为0分钟
4号乘客和1号乘客到达时间相同,排在1号乘客后面,因载客量未能乘09:10这班车,直到放弃时间没有公交车前来,则放弃乘坐
5号乘客直到放弃时间没有公交车前来,则放弃乘坐
6号乘客到站直接乘坐08:30这班车,等待时长为0分钟