8963: 寻找座位
[Creator : ]
Description
园博会的展区面积很大,接驳不同展区间的电动车需要提前预约,参观者凭成功预约信息才能坐车。因此发车前会进行频繁的订票/退票操作。
现在有一辆特殊电动车,里面有 $n$ 排,每排 $5$ 个座位,每个座位用 $1$ 表示已预订,$0$ 表示未预订。
小明负责安排这辆车下一趟座位,按时间顺序收到 $m$ 个操作,其中 $D$ 表示订票,$T$ 表示退票。
请你帮助小明编写程序,看剩余座位是否能满足每一个要求。
现在有一辆特殊电动车,里面有 $n$ 排,每排 $5$ 个座位,每个座位用 $1$ 表示已预订,$0$ 表示未预订。
小明负责安排这辆车下一趟座位,按时间顺序收到 $m$ 个操作,其中 $D$ 表示订票,$T$ 表示退票。
请你帮助小明编写程序,看剩余座位是否能满足每一个要求。
Input
第一行是两个正整数 $n,m$,含义入题意。
接下来是 $n$ 行,每行 $5$ 个数字,表示座位是否被占用,$0$ 表示未占用,$1$ 表示已经占用。
$n$ 行座位信息后是 $m$ 行操作,每个操作包含一个字符和一个数字,其中 $D$ 表示订票,$T$ 表示退票。
例如
接下来是 $n$ 行,每行 $5$ 个数字,表示座位是否被占用,$0$ 表示未占用,$1$ 表示已经占用。
$n$ 行座位信息后是 $m$ 行操作,每个操作包含一个字符和一个数字,其中 $D$ 表示订票,$T$ 表示退票。
例如
D 5表示要预订 $5$ 张票
T 2表示退订 $2$ 张票
Output
针对 $m$ 个订票/退票操作,按照顺序给出座位是否满足需求的判断结果。Yes 表示可以满足要求,No 表示不能满足。
Constraints
对于全部数据,有 $1 \leq n \leq 1,000,\ 1 \leq m \leq 10^5,\ 1 \leq $ 单次订票退票数量 $\leq 10,000$。
Sample 1 Input
6 4
11111
11101
11011
11111
10001
10001
D 5
T 2
D 6
T 3
Sample 1 Output
Yes
Yes
No
Yes
开始的时候,已经预订了 $22$ 个位置,有 $8$ 个位置可用。
第一次 D 5,表示要订 $5$ 张票,因此可以满足,输出 Yes。现在预订了 $27$ 个位置,有 $3$ 个位置可用。
第二次 T 2,表示要退 $2$ 张票,因此可以满足,输出 Yes。现在预订了 $25$ 个位置,有 $5$ 个位置可用。
第三次 D 6,表示要退 $6$ 张票,不能满足,输出 No。现在预订了 $25$ 个位置,有 $5$ 个位置可用。
第四次 T 3,表示要退 $3$ 张票,因此可以满足,输出 Yes。现在预订了 $22$ 个位置,有 $8$ 个位置可用。
第一次 D 5,表示要订 $5$ 张票,因此可以满足,输出 Yes。现在预订了 $27$ 个位置,有 $3$ 个位置可用。
第二次 T 2,表示要退 $2$ 张票,因此可以满足,输出 Yes。现在预订了 $25$ 个位置,有 $5$ 个位置可用。
第三次 D 6,表示要退 $6$ 张票,不能满足,输出 No。现在预订了 $25$ 个位置,有 $5$ 个位置可用。
第四次 T 3,表示要退 $3$ 张票,因此可以满足,输出 Yes。现在预订了 $22$ 个位置,有 $8$ 个位置可用。