#2712. 共享单车

共享单车

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

校园里面的共享单车实在是太混乱了,因此需要在校园里面设置共享单车站,同学们可以去车站里面排队申请使用共享单车,或者停放共享单车。排队用车的过程如下:如果有一辆共享单车,那么队列的第一名就可 以立刻骑上它,否则队列中的人就要继续等待直到有人把共享单车停进车站。车站可以容纳任意数量的单车。

令每一名同学的等待时间为其请求用车(即进入队列)的时刻到其取得共享单车之间花费的时间。如果这名同学没有得到一辆共享单车,那么他的等待时间为无穷大,总等待时间是每名同学等待时间之和。

如果已经直到所有人每天用车的时间表,知道同学们每天什么时候申请骑车以及停放单车,只有每天的开始时车站放置了多少量单车是未知的。

给出q\red{q}个询问,当开始时放置的共享单车为bi\red{b_i}的情况下的总等待时间时多少?

输入格式

第一行输入两个整数n,q\red{n,q,}分别表示用车需求以及停放的总数和询问的数量。

接下来n\red{n}行描述了每一次的操作,格式如下所示:

"+ t k\red{+ ~t~ k}"表示在时刻t\red{t,}k\red{k}辆单车停放;

" t k\red{-~ t ~k}"表示在时刻t\red{t,}k\red{k}两单车取用

最后一行给出q\red{q}个询问bi\red{b_i,}表示一天开始时的单车数量

(操作按照时刻递增的顺序给出)

输出格式

包含q\red{q}行,分别对应每一次询问的答案。如果等待的总时间是无限长,那么输出"INFINITY\red{INFINITY}"

样例

输入样例

5 4 
- 1 1 
- 2 2 
+ 4 1 
- 6 1 
+ 7 2 
0 3 1 2

输出样例

INFINITY 
0 
8 
3

提示

对于100%\red{100\%}的数据 ,1<=n,q<=105,1<=t<=109\red{1<=n,q<=10^5,1<=t<=10^9};1<=k<=104\red{1<=k<=10^4};0<=bi<=109\red{0<=b_i<=10^9};

其中40%\red{40\%}的数据满足 ,1<=n,q<=10,1<=t<=100\red{1<=n,q<=10,1<=t<=100};1<=k<=100\red{1<=k<=100};0<=bi<=500\red{0<=b_i<=500};

普及组测试5

未参加
状态
已结束
规则
IOI
题目
4
开始于
2022-8-13 18:00
结束于
2022-8-13 21:00
持续时间
3 小时
主持人
参赛人数
46