← 返回题目列表

Codeforces · 975/C

C. 瓦尔哈拉围攻

中文机器翻译题面 查看原题

无骨者伊瓦尔是一位伟大的领袖。他正试图从拉格萨手中夺取卡特加特海峡。战争已经开始,一波又一波伊瓦尔的战士在战斗中倒下。

Ivar 有 $$$n$$$ 个战士,他将他们放在大门前的一条直线上,使得第 $$$i$$$ 个战士站在第 $$$(i-1)$$$ 个战士之后。第一个战士领导进攻。

每个攻击者在倒地之前最多可以承受 $$$a_i$$$ 箭,其中 $$$a_i$$$ 是第 $$$i$$$ 个战士的力量。

拉格莎命令她的战士们在第$$$i$$$分钟内射出$$$k_i$$$箭,箭一支接一支地击中了第一个仍然站立的战士。当伊瓦尔的所有战士倒下,飞来的箭全部飞过之后,雷神托尔砸碎了他的锤子,所有伊瓦尔的战士都恢复了之前的力量,重新站起来战斗。换句话说,如果所有战士在$$$t$$$分钟内死亡,那么他们将在$$$t$$$分钟结束时全部站起来战斗。

战斗将持续 $$$q$$$ 分钟,每分钟后你应该告诉 Ivar 他的站立战士数量是多少。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \leq 200\,000$$$) — 战士的数量和战斗的分钟数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) 代表战士的实力。

第三行包含$$$q$$$整数$$$k_1, k_2, \ldots, k_q$$$ ($$$1 \leq k_i \leq 10^{14}$$$),其中第$$$i$$$代表Lagertha在第$$$i$$$第$$$i$$$的顺序:$$$k_i$$$箭头将攻击战士。

输出

输出$$$q$$$行,其中第$$$i$$$行是第$$$i$$$第$$$i$$$后站立战士的数量。

示例

输入 #1

5 5
1 2 1 2 1
3 10 1 1 1

输出 #1

3
5
4
4
3

输入 #2

4 4
1 2 3 4
9 1 10 6

输出 #2

1
4
4
1

注意

在第一个示例中:

- 第 1 分钟后,第 1 名和第 2 名战士死亡。
- 第 2 分钟后所有战士都死了(剩下的所有箭都浪费了),然后他们将复活,因此答案是 5 – 所有战士都活着。
- 第 3 分钟后,第 1 个战士死亡。
- 第4分钟后,第二个战士受到打击,力量减少1。
- 第 5 分钟后,第二个战士死亡。