logo AlgoBeat OnlineJudge
登录 注册

#216078. [CSPro 33] 十滴水

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

洛谷的测试数据仅供民间交流使用,非官方测试数据。官方评测链接:https://www.cspro.org/


十滴水是一个非常经典的小游戏。

:::align{center} :::

小 C 正在玩一个一维版本的十滴水游戏。我们通过一个例子描述游戏的基本规则。

游戏在一个 的网格上进行,格子用整数 编号,编号从左往右依次递增。网格内 个格子里有 滴水,其余格子里没有水。在我们的例子中,,按照编号顺序,每个格子中分别有 滴水。

玩家可以进行若干次操作,每次操作中,玩家选择一个有水的格子,将格子的水滴数加一。任何时刻若某个格子的水滴数大于等于 ,这个格子里的水滴就会向两侧爆开。此时,这个格子的水被清空,同时对于左方、右方两个方向同时进行以下操作:找到当前格子在对应方向上最近的有水的格子,如果存在这样的格子,将这个格子的水滴数加一。若在某个时刻,有多个格子的水滴数大于等于 ,则最靠左的先爆开。

在我们的例子中,若玩家对第三格进行操作,则其水滴数变为 ,故第三格水滴爆开,水被清空,其左侧最近的有水格子(第二格)和右侧最近的有水格子(第四格)的水量增加 ,此时每个格子中分别有 滴水。

此时第二格和第四格的水滴数均大于等于 ,按照规则,第二格的水先爆开,爆开后每个格子中分别有 滴水;最后第四格的水滴爆开,每个格子中分别有 滴水。

小 C 开始了一局游戏并进行了 次操作。小 C 在每次操作后,会等到所有水滴数大于等于 的格子里的水滴都爆开再进行下一次操作。

小 C 想知道他的水平有多高,于是他想知道每一次操作后还有多少格子里有水。

保证这 次操作都是合法的,即每次操作时操作的格子里都有水。

输入格式

从标准输入读入数据。

输入的第一行三个整数 分别表示网格宽度、有水的格子个数以及操作次数。

接下来 行每行两个整数 ,表示第 格有 滴水。

接下来 行每行一个整数 ,表示小 C 对第 格做了一次操作。

输出格式

输出到标准输出。

输出 行,每行一个整数表示这次操作之后网格上有水的格子数量。

样例

样例输入 1

5 5 2
1 2
2 4
3 4
4 4
5 2
3
1

样例输出 1

2
1

数据范围与提示

子任务

对于所有测试数据,

  • 输入的所有 两两不同;
  • 对于每个输入的 ,保证在对应操作时 内有水。
子任务编号 特殊性质 分值
1 15
2 ^
3 ^ ^ 10
4 ^ 15
5 ^
6 ^
7 ^

特殊性质:在游戏的任意时刻(包括水滴爆开的连锁反应过程中),只有至多一个格子的水滴数大于等于