AT_abc258_e [ABC258E] Packing Potatoes

题目描述

有 $10^{100}$ 个土豆依次在传送带上流过，每次流过一个。每个土豆的重量由长度为 $N$ 的数列 $W = (W_0, \dots, W_{N-1})$ 给出，第 $i\ (1 \leq i \leq 10^{100})$ 个流过的土豆的重量为 $W_{(i-1) \bmod N}$。这里，$(i-1) \bmod N$ 表示 $i-1$ 除以 $N$ 的余数。

高桥君首先准备一个空箱子，并按照以下规则依次将土豆装入箱中：

• 将土豆放入箱子中。如果箱中土豆的总重量达到或超过 $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$ 个询问的答案。

输入输出样例 #1

输入 #1

3 2 5
3 4 1
1
2

输出 #1

2
3

输入输出样例 #2

输入 #2

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

输出 #2

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)$
• 所有输入均为整数

样例解释 1

高桥君在盖上第 $2$ 个箱子之前的操作如下：

• 准备一个空箱子。
• 将第 $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$ 个土豆。

由 ChatGPT 4.1 翻译