#P8188. [USACO22FEB] Email Filing S

[USACO22FEB] Email Filing S

题目描述

Farmer John has fallen behind on organizing his inbox. The way his screen is organized, there is a vertical list of folders on the left side of the screen and a vertical list of emails on the right side of the screen. There are MM total folders, numbered 1M1 \ldots M (1M104)(1 \le M \le 10^4). His inbox currently contains NN emails numbered 1N1\ldots N (1N105)(1 \le N \le 10^5); the iith email needs to be filed into folder fif_i (1fiM)(1\le f_i\le M).

FJ's screen is rather small, so he can only view KK (1Kmin(N,M))(1\le K\le \min(N,M)) folders and KK emails at once. Initially, his screen starts out displaying folders 1K1 \ldots K on the left and emails 1K1 \ldots K on the right. To access other folders and emails, he needs to scroll through these respective lists. For example, if he scrolls down one position in the list of folders, his screen will display folders 2K+12 \ldots K+1, and then scrolling down one position further it will display folders 3K+23 \ldots K+2. When FJ drags an email into a folder, the email disappears from the email list, and the emails after the one that disappeared shift up by one position. For example, if emails 1,2,3,4,51, 2, 3, 4, 5 are currently displayed and FJ drags email 3 into its appropriate folder, the email list will now show emails 1,2,4,5,61, 2, 4, 5, 6. FJ can only drag an email into the folder to which it needs to be filled.

Unfortunately, the scroll wheel on FJ's mouse is broken, and he can only scroll downwards, not upwards. The only way he can achieve some semblance of upward scrolling is if he is viewing the last set of KK emails in his email list, and he files one of these. In this case, the email list will again show the last KK emails that haven't yet been filed, effectively scrolling the top email up by one. If there are fewer than KK emails remaining, then all of them will be displayed.

Please help FJ determine if it is possible to file all of his emails.

输入格式

The first line of input contains TT (1T10)(1≤T≤10), the number of subcases in this input, all of which must be solved correctly to solve the input case. The TT subcases then follow. For each subcase, the first line of input contains M,NM,N and KK. The next line contains f1fNf_1\cdots f_N.

It is guaranteed that the sum of MM over all subcases does not exceed 10410^4, and that the sum of NN over all subcases does not exceed 10510^5.

输出格式

Output TT lines, each one either containing either YES or NO, specifying whether FJ can successfully file all his emails in each of the TT subcases.

题目大意

题目描述

FarmerJohnFarmer John 在整理收件箱方面已经落后了。他的屏幕排列方式是,屏幕左侧有一个垂直的文件夹列表,屏幕右侧有一个垂直的电子邮件列表。共有 MM 个文件夹,编号为 1M(1M104)1 \dotsm M (1 \le M \le 10^4) 。他的收件箱当前包含 NN 封编号为 1N(1N105)1 \dotsm N (1 \le N \le 10^5) 的电子邮件;第 ii 封电子邮件需要归档到文件夹 fi(1fiM)f_i (1 \le f_i \le M)

FJFJ 的屏幕有些小,所以他同时只能查看 K(1Mmin(n,m))K(1 \le M \le min(n,m))个文件夹和 KK 封电子邮件。最初,他的屏幕左侧显示文件夹 1K1 \dotsm K,右侧显示电子邮件 1K1 \dotsm K。要访问其他文件夹和电子邮件,他需要滚动相应的列表。例如,如果他将文件夹列表向下滚动一个位置,他的屏幕将显示文件夹 2K+12 \dotsm K+1,然后再向下滚动一个位置将显示文件夹 3K+23 \dotsm K+2。当 FJFJ 将一封电子邮件拖曳至一个文件夹时,该电子邮件将从电子邮件列表中消失,并且消失的电子邮件之后的电子邮件会向上移动一个位置。例如,如果当前显示的是电子邮件 1,2,3,4,51,2,3,4,5,然后 FJFJ 将电子邮件 33 拖曳至其对应的文件夹中,则电子邮件列表现在将显示电子邮件 1,2,4,5,61,2,4,5,6FJFJ 只可以将电子邮件拖曳至其需要归档的文件夹中。

不幸的是,FJFJ 的鼠标滚轮坏了,所以他只能向下滚动,不能向上滚动。他可以实现类似向上滚动的唯一情况是,他正在查看他的电子邮件列表中的最后 KK 封电子邮件,并且他归档了其中的一封。在这种情况下,电子邮件列表将再继续显示尚未归档的最后 KK 封电子邮件,实际上使得最上方的电子邮件向上滚动了一个位置。如果剩余少于 KK 封电子邮件,则将显示所有电子邮件。

请帮助 FJFJ 判断是否可能归档他的所有电子邮件。

输入格式

输入的第一行包含 T(1T10)T (1 \le T \le 10),为当前测试用例中的子测试用例数量,所有子测试用例必须全部正确才能通过当前测试用例。以下是 TT 个子测试用例。每一个子测试用例的第一行包含 MMNNKK。第二行包含 f1fNf_1…f_N

输入保证所有子测试用例的 MM 之和不超过 10410^4,所有子测试用例的 NN 之和不超过 10510^5

输出格式

输出 TT 行,每行包含 "YES" 或 "NO",表示对于 TT 个子测试用例中的每一个,FJFJ 是否可以成功归档他的所有电子邮件。

数据范围

  • 测试点 2-10 中,所有子测试用例的 MM 之和不超过 10310^3
  • 测试点 11-12 没有额外限制。
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

提示

【数据范围】

  • In inputs 2-10, the sum of MM over all subcases does not exceed 10310^3.
  • In inputs 11-12, no additional constraints.