Email Filing

题目描述

农夫约翰在整理收件箱方面落后了。他的屏幕布局如下：屏幕左侧是一列竖直的文件夹列表，右侧是一列竖直的邮件列表。共有 $M$ 个文件夹，编号为 $1 \ldots M$（$1 \le M \le 10^4$）。他的收件箱当前包含 $N$ 封邮件，编号为 $1\ldots N$（$1 \le N \le 10^5$）；第 $i$ 封邮件需要被归档到文件夹 $f_i$（$1\le f_i\le M$）。 由于 FJ 的屏幕很小，他一次只能查看 $K$（$1\le K\le \min(N,M)$）个文件夹以及 $K$ 封邮件。初始时，屏幕左侧显示文件夹 $1 \ldots K$，右侧显示邮件 $1 \ldots K$。要访问其他文件夹和邮件，他需要分别在这两个列表中滚动。例如，如果他在文件夹列表中向下滚动一格，屏幕将显示文件夹 $2 \ldots K+1$；再向下滚动一格，则显示文件夹 $3 \ldots K+2$。 当 FJ 将一封邮件拖入某个文件夹时，这封邮件会从邮件列表中消失，而其后的邮件会整体向上移动一格。例如，如果当前显示邮件 $1, 2, 3, 4, 5$，且 FJ 将邮件 3 拖入其对应的文件夹，那么邮件列表将变为显示邮件 $1, 2, 4, 5, 6$。FJ 只能将邮件拖入它需要被归档到的那个文件夹。 不幸的是，FJ 的鼠标滚轮坏了，他只能向下滚动，不能向上滚动。他唯一能够实现某种“向上滚动”的方式是：当他正在查看邮件列表中最后一组 $K$ 封邮件时，若他归档了其中一封邮件，则邮件列表会再次显示尚未归档的最后 $K$ 封邮件，相当于将最上方显示的邮件向上移动了一格。如果剩余邮件少于 $K$ 封，则会显示剩余的全部邮件。 请帮助 FJ 判断他是否有可能将所有邮件都成功归档。

输入格式

第一行输入包含 $T$（$1 \le T \le 10$），表示本次输入包含的子测试组数；要通过该输入用例，必须将这 $T$ 个子测试全部正确解决。 接下来是 $T$ 个子测试。对于每个子测试，第一行包含 $M$、$N$ 和 $K$。下一行包含 $f_1 \ldots f_N$。 保证所有子测试中 $M$ 的总和不超过 $10^4$，且 $N$ 的总和不超过 $10^5$。

输出格式

输出 $T$ 行，每行输出 YES 或 NO，用于表示在对应的子测试中 FJ 是否能够成功归档所有邮件。

6
5 5 1
1 2 3 4 5
5 5 1
1 2 3 5 4
5 5 1
1 2 4 5 3
5 5 2
1 2 4 5 3
3 10 2
1 3 2 1 3 2 1 3 2 1
3 10 1
1 3 2 1 3 2 1 3 2 1

YES
YES
NO
YES
YES
NO

提示

SCORING: 在第 2-10 号输入中，所有子测试中 $M$ 的总和不超过 $10^3$。 在第 11-12 号输入中，没有额外限制。 题目来源：Brian Dean

标签: USACO|2022|Silver

来源

USACO|2022|Silver