Candy Cane Feast

题目描述

Farmer John 的奶牛们非常爱吃甜食，尤其喜欢吃拐杖糖！FJ 一共有 $N$ 头奶牛，每头都有一个初始身高；他想给它们喂 $M$ 根拐杖糖，每根拐杖糖也有不同的高度（$1\le N,M\le 2\cdot 10^5$）。

FJ 计划按输入给出的顺序，一根一根地喂拐杖糖。为了给奶牛们喂一根拐杖糖，他会把拐杖糖悬挂起来，使得拐杖糖在开始时刚好接触地面。然后奶牛会按输入给出的顺序依次排队，走到拐杖糖前，每头奶牛最多吃到自己身高的高度（因为它们够不到更高的部分）。拐杖糖会保持在最初悬挂的位置，不会因为奶牛吃掉了底部而被放低到地面。若拐杖糖的底端已经高于某头奶牛的身高，则该奶牛在轮到时可能什么也吃不到。

当每头奶牛都轮到之后，奶牛会按照自己吃掉的拐杖糖长度增长相应的身高。随后 Farmer John 挂起下一根拐杖糖，奶牛们再次重复该过程（下一根拐杖糖仍从 1 号奶牛开始吃）。

输入格式

第一行包含 $N$ 和 $M$。 第二行包含 $N$ 头奶牛的初始身高，每个都在区间 $[1,10^9]$。 第三行包含 $M$ 根拐杖糖的高度，每个都在区间 $[1,10^9]$。

输出格式

输出 $N$ 行，分别为每头奶牛的最终身高。 注意：本题涉及的整数可能很大，可能需要使用 64 位整数类型（例如 C/C++ 中的 "long long"）。

3 2
3 2 5
6 1

7
2
7

提示

第一根拐杖糖高度为 $6$。 第一头奶牛吃掉第一根拐杖糖从底部起直到高度 $3$ 的部分，之后第一根拐杖糖剩余部分位于高度区间 $[3,6]$。 第二头奶牛身高不够，无法吃到第一根拐杖糖的任何剩余部分。 第三头奶牛再吃掉第一根拐杖糖的 $2$ 个单位。第一根拐杖糖剩余部分位于高度区间 $[5,6]$，没有被吃掉。 接下来，每头奶牛按自己吃掉的数量增长，因此奶牛身高变为 $[3+3, 2+0, 5+2]=[6, 2, 7]$。 第二根拐杖糖高度为 $1$，第一头奶牛把它全部吃掉。 SCORING: Inputs 2-10: $N, M \le 10^3$ Inputs 11-14: 无额外限制。 题目作者：Agastya Goel

标签: USACO|2023|Bronze

来源

USACO|2023|Bronze