이메일 정리

농부 존은 받은 편지함 정리를 미뤄 왔다. 그의 화면 구성은, 화면 왼쪽에 폴더들의 세로 목록이 있고 화면 오른쪽에 이메일들의 세로 목록이 있다. 폴더는 총 \(M\)개로 \(1 \ldots M\) (\(1 \le M \le 10^4)\)로 번호가 붙어 있다. 받은 편지함에는 현재 \(1\ldots N\)으로 번호가 붙은 \(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가 모든 이메일을 분류할 수 있는지 판별하도록 도와주자.

출제자: Brian Dean

배점

• 입력 2-10에서는 모든 하위 케이스에 대한 \(M\)의 합이 \(10^3\)을 넘지 않는다.
• 입력 11-12에는 추가 제약이 없다.

출제자: Brian Dean

첫째 줄에 이 입력에 포함된 하위 케이스의 수 \(T\) (\(1 \le T \le 10\))가 주어지며, 입력 케이스를 해결하려면 모든 하위 케이스를 올바르게 풀어야 한다. 이어서 \(T\)개의 하위 케이스가 주어진다. 각 하위 케이스의 첫째 줄에 \(M\), \(N\), \(K\)가 주어진다. 다음 줄에 \(f_1 \ldots f_N\)이 주어진다.

모든 하위 케이스에 대한 \(M\)의 합이 \(10^4\)를 넘지 않고, 모든 하위 케이스에 대한 \(N\)의 합이 \(10^5\)를 넘지 않음이 보장된다.

\(T\)개의 줄을 출력하며, 각 줄에는 \(T\)개의 하위 케이스 각각에 대해 FJ가 모든 이메일을 성공적으로 분류할 수 있는지에 따라 YES 또는 NO를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2021-2022 > February > Silver