Draw Your Cards

题目描述

有一副由 $N$ 张面朝下的卡片组成的牌堆，上面分别写着 $1$ 到 $N$ 的整数。 从顶部数第 $i$ 张卡片上写着的整数是 $P_i$。 使用这副牌，你将执行 $N$ 次操作，每次操作包含以下步骤：

抽取牌堆最顶部的卡片。 设 $X$ 为其上写的整数。 将抽取的卡片面朝上，叠放到桌上那些面朝上且在最上面的卡片中，写着的整数大于或等于 $X$ 的卡片中整数最小的一张上。如果桌上没有这样的卡片，则将抽取的卡片面朝上放在桌上，而不叠放到任何卡片上。 然后，如果桌上存在由 $K$ 张面朝上的卡片构成的一叠，则吃掉所有那些卡片。 被吃掉的卡片都会从桌上消失。

对于每一张卡片，找出是哪一次的第 $N$ 次操作吃掉了它。 如果该卡片直到结束都没有被吃掉，则报告该情况。

输入格式

输入从标准输入给出，格式如下： $N$ $K$ $P_1$ $P_2$ $\dots$ $P_N$

输出格式

输出 $N$ 行。
第 $i$ 行（$1 \le i \le N$）应描述写有整数 $i$ 的那张卡片。 具体地，

如果写有 $i$ 的卡片在第 $x$ 次操作中被吃掉，则输出 $x$； 如果该卡片在任何操作中都未被吃掉，则输出 $-1$。

5 2
3 5 2 1 4

4
3
3
-1
4

5 1
1 2 3 4 5

1
2
3
4
5

15 3
3 14 15 9 2 6 5 13 1 7 10 11 8 12 4

9
9
9
15
15
6
-1
-1
6
-1
-1
-1
-1
6
15

提示

输入中的所有数值均为整数。 $1 \le K \le N \le 2 \times 10^5$ $P$ 是 $(1,2,\dots,N)$ 的一个置换（即通过重新排列 $(1,2,\dots,N)$ 得到的序列）。在此输入中，$P=(3,5,2,1,4)$ 且 $K=2$。

在第 $1$ 次操作中，写有 $3$ 的卡片被放到桌上，面朝上，未叠放到任何卡片上。 在第 $2$ 次操作中，写有 $5$ 的卡片被放到桌上，面朝上，未叠放到任何卡片上。 在第 $3$ 次操作中，写有 $2$ 的卡片被面朝上叠放到写有 $3$ 的卡片上。 现在有一叠由 $K=2$ 张面朝上的卡片构成，最上面写着 $2$，下面写着 $3$，因此这些卡片被吃掉了。

在第 $4$ 次操作中，写有 $1$ 的卡片被面朝上叠放到写有 $5$ 的卡片上。 现在有一叠由 $K=2$ 张面朝上的卡片构成，最上面写着 $1$，下面写着 $5$，因此这些卡片被吃掉了。

在第 $5$ 次操作中，写有 $4$ 的卡片被放到桌上，面朝上，未被叠放到任何卡片上。 写有 $4$ 的卡片直到结束都没有被吃掉。
如果 $K=1$，每张卡片在放到桌上后会在同一次操作中立即被吃掉。

标签: AtCoder|abc260D

来源

AtCoder|abc260D