P2052【USACO 2013 January Gold】座位 | ||
|
问题描述
奶牛们开了一家餐馆。该餐馆里有N(1 <= N <= 500,000)个排成一列的座位(编号1到N),编号越小的座位越靠近窗户。早晨开业时,座位都是空的。
今天餐馆里发生了M(1 <= M <= 300,000)个事件,这些事件总共分两类:
1.一伙人一起来就餐,该伙人共P(1 <= p <= N)个人,这伙人想坐在一段连续的位置上就餐,如果能坐下,他们希望座位尽量靠近窗户。如果无法坐下,他们会马上离开。
2.坐在a号到b号(1 <= a <= b <= N) 这连续一段座位的客人用餐完毕后离开了。
请帮贝西计算今天有多少伙人因为没有满足他们要求的座位而离开了。
输入格式
第一行,两个空格间隔的整数N和M
接下来M行,按时间先后描述了今天发生的事件:
字母A和一个整数P表示一伙P个人到达的餐馆。
字母L和两个整数a,b表示a到b这一段位置的客人离开了。
输出格式
一个整数,表示所求的结果
样例输入
10 4
A 6
L 2 4
A 5
A 2
样例输出
1
来源 感谢Formiko提供一组坑爹数据卡了一帮人