← 返回题目列表

Codeforces · 2172/J

J. 滑动瓷砖

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

您在 $$$n \times n$$$ 网格上玩了一个特殊的滑动谜题。这个谜题与标准滑动谜题略有不同:在每对相邻的列之间,有一个高度为 $$$h_i$$$ 的垂直条(对于 $$$1 \leq i \lt n$$$)位于网格底部。每个 $$$h_i$$$ 表示该条从底部向上延伸了多少行,并且它阻止了这些行中两列之间的图块移动。

网格包含多个图块,每个图块正好占据一个单元格。这些图块可以在网格中自由滑动,除非它们被网格边界、垂直条(取决于其高度)或另一个图块阻挡。

拼图允许两种类型的倾斜操作:

  • 向右倾斜:所有图块尽可能向右滑动。
  • 向下倾斜:所有瓷砖尽可能向下滑动。

在这两种操作中,所有图块同时移动,并且仅在被网格边缘、条形或其他图块阻挡时才停止。

图 1:示例输入 1 的图示。

将组操作定义为以下序列:首先将网格向右倾斜,然后向下倾斜。

最初,第 $$$i$$$ 列有从该列底部堆叠的 $$$a_i$$$ 瓷砖。您只需在板上执行一次组操作即可。运算结束后,确定每列的图块数量。

输入

第一行包含一个整数$$$n$$$,代表棋盘的大小。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$,其中 $$$a_i$$$ 是最初第 $$$i$$$ 列中的图块数量。

第三行包含 $$$n-1$$$ 整数 $$$h_1,h_2,\ldots,h_{n-1}$$$,其中 $$$h_i$$$ 是列 $$$i$$$ 和列 $$$i+1$$$ 之间的条形高度。

  • $$$2 \le n \le 5 \times 10^5$$$
  • $$$0 \le a_i \le n$$$
  • $$$0 \le h_i \le n-1$$$

输出

在新行中打印 $$$n$$$ 数字,表示执行一次分组操作后每列中的图块数量。

示例

输入
复制

5
5 5 2 3 0
3 0 4 1

输出
复制

3 3 4 2 3

输入
复制

6
4 3 0 3 0 2
1 0 0 1 3

输出
复制

1 0 3 3 2 3