← 返回题目列表

Codeforces · 1468/B

B. 面包店

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

Monocarp 想在他当地开一家面包店。但首先,他应该弄清楚自己是否可以与其他商店竞争。

Monocarp 计划面包店将营业 $$$n$$$ 天。在第 $$$i$$$ 天,$$$a_i$$$ 面包将在开业前的早上烘烤。在第 $$$n$$$ 天结束时,Monocarp 将以大幅折扣出售之前未售出的所有剩余面包。

由于面包的储存方式,面包店卖家按以下顺序出售面包:首先,他出售当天早上烤好的面包;然后,他出售面包。其次,他把前一天烤好的还没卖掉的面包卖掉;还有两天前烤好的还没卖的面包,等等。这就是为什么有些顾客可能会购买不新鲜的面包,并且肯定会散布负面谣言。

让我们将面包腐败定义为烘烤之日与出售之日之间的差异。那么面包店的不吸引力将等于该面包店烘焙的所有面包中最大的腐败程度。

假设Monocarp当地的消费者需求为$$$k$$$,则意味着每天会有$$$k$$$顾客来到面包店,每人会索要一条面包(面包按照上述顺序出售)。如果没有剩下面包,那么这个人就不会买任何东西。在最后一天的销售中,所有剩余的面包都将被出售(并且它们仍将计入不吸引力的计算中)。

Monocarp 分析了竞争对手的数据,得出了 $$$m$$$ 可能的消费者需求值 $$$k_1, k_2, \dots, k_m$$$,现在他想计算面包店对于每个需求值的不吸引力。你能帮助他吗?

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$; $$$1 \le m \le 2 \cdot 10^5$$$) - 面包店营业的天数和消费者需求的可能值的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 每天要烘烤的面包数量。

第三行包含 $$$m$$$ 整数 $$$k_1, k_2, \dots, k_m$$$ ($$$1 \le k_1 < k_2 < \dots < k_m \le 10^9$$$) — 按升序排列的可能的消费者需求值。

输出

打印 $$$m$$$ 整数:针对每个消费者需求,打印面包店的不吸引力。

示例

输入 #1

5 4
5 2 1 3 7
1 3 4 10

输出 #1

4 2 1 0

输入 #2

8 9
3 1 4 1 5 9 2 6
1 2 3 4 5 6 7 8 9

输出 #2

7 5 3 3 2 1 1 1 0

注意

在第一个示例中,我们来描述几个消费者需求会发生什么:

如果消费者需求等于 $$$1$$$:

- 在 $$$1$$$ 当天:$$$5$$$ 面包被烘烤,仅售出 $$$1$$$,损坏程度等于 $$$1 - 1 = 0$$$;
- 在 $$$2$$$ 那天:留下了 $$$4$$$ 面包,并烘烤了更多 $$$2$$$ 面包。只售出了 $$$1$$$ 面包,而且是今天烤的面包,已经变质了 $$$2 - 2 = 0$$$;
- 在 $$$3$$$ 天:第一天的 $$$4$$$ 面包和第二天的 $$$1$$$ 面包。今天又烤了一条面包,并在变质的情况下售出 $$$3 - 3 = 0$$$;
- 在 $$$4$$$ 天:第一天的 $$$4$$$ 面包和第二天的 $$$1$$$ 面包。 $$$3$$$ 又烤了面包,其中一个在今天售出并已变质 $$$4 - 4 = 0$$$;
- 在$$$5$$$天:第一天的$$$4$$$面包,第二天的$$$1$$$面包和第四天的$$$2$$$面包。又烤了 $$$7$$$ 面包,由于是最后一天,所有 $$$14$$$ 面包都卖完了。从第一天开始,$$$4$$$ 面包的最大腐败程度等于 $$$5 - 1 = 4$$$。

如果消费者需求等于 $$$10$$$,则所有烘焙面包将在烘焙当天售出,并且损坏程度等于 $$$0$$$。