Packing Potatoes

题目描述

$10^{100}$ 个土豆将一个接一个地从传送带上过来。土豆的重量由长度为 $N$ 的序列 $W = (W_0, \dots, W_{N-1})$ 描述：第 $i$ 个到来的土豆的重量为 $W_{(i-1) \bmod N}$，其中 $(i-1) \bmod N$ 表示 $i-1$ 除以 $N$ 的余数。 Takahashi 会准备一个空箱子，然后按顺序装土豆，规则如下。

将到来的土豆装入箱中。如果箱中土豆的总重量现在为 $X$ 或更大，就封住该箱并准备一个新的空箱子。

给你 $Q$ 个查询。在第 $i$ 个查询 $(1 \leq i \leq Q)$ 中，给定一个正整数 $K_i$，求第 $K_i$ 个被封的箱子中土豆的数量。在题目的约束下可以证明，至少会有 $K_i$ 个被封的箱子。

输入格式

输入按照下列格式从标准输入给出： $N$ $Q$ $X$ $W_0$ $W_1$ $\ldots$ $W_{N-1}$ $K_1$ $\vdots$ $K_Q$

输出格式

打印 $Q$ 行。第 $i$ 行 $(1 \leq i \leq Q)$ 应包含第 $i$ 个查询的答案。

3 2 5
3 4 1
1
2

2
3

10 5 20
5 8 5 9 8 7 4 4 8 2
1
1000
1000000
1000000000
1000000000000

4
5
5
5
5

提示

$1 \leq N, Q \leq 2 \times 10^5$ $1 \leq X \leq 10^9$ $1 \leq W_i \leq 10^9 \, (0 \leq i \leq N - 1)$ $1 \leq K_i \leq 10^{12} \, (1 \leq i \leq Q)$ 输入中的所有值均为整数。在封第 $2$ 个箱子之前，Takahashi 会做如下操作：

准备一个空箱子。 将第 $1$ 个土豆装入箱中。现在箱中土豆的总重量是 $3$。 将第 $2$ 个土豆装入箱中。现在箱中土豆的总重量是 $3 + 4 = 7$，这不小于 $X = 5$，因此封住该箱。 准备一个新的空箱子。 将第 $3$ 个土豆装入箱中。现在箱中土豆的总重量是 $1$。 将第 $4$ 个土豆装入箱中。现在箱中土豆的总重量是 $1 + 3 = 4$。 将第 $5$ 个土豆装入箱中。现在箱中土豆的总重量是 $1 + 3 + 4 = 8$，这不小于 $X = 5$，因此封住该箱。

第 $1$ 个被封的箱子包含 $2$ 个土豆，第 $2$ 个被封的箱子包含 $3$ 个土豆。

标签: AtCoder|abc258E

来源

AtCoder|abc258E