레이팅 미적용농부 존은 \(1\)번부터 \(N\)번까지 번호가 붙은 \(N\) (\(1 \leq N \leq 2 \cdot 10^5\))개의 농장을 가지고 있다. 존은 농장 \(i\)를 시각 \(c_i\)에 닫는다고 알려져 있다. 베시는 시각 \(S\)에 일어나서, 농장들이 닫히기 전에 가능한 한 많은 농장을 방문하여 하루의 생산성을 최대화하고 싶다. 베시는 농장 \(i\)를 시각 \(t_i + S\)에 방문할 계획이다. 농장을 실제로 방문하려면 농부 존이 그 농장을 닫기 전에 엄격히 먼저 도착해야 한다.
베시에게는 \(Q\) \((1 \leq Q \leq 2 \cdot 10^5)\)개의 질의가 있다. 각 질의에서 두 정수 \(S\)와 \(V\)가 주어진다. 각 질의에 대해, 베시가 시각 \(S\)에 일어났을 때 적어도 \(V\)개의 농장을 방문할 수 있는지 출력하여라.
출제: Chongtian Ma
배점
- 입력 2-4: \(N,Q\le 10^3\)
- 입력 5-9: \(c_i, t_i \le 20\)
- 입력 10-17: 추가 제약 없음.
출제: Chongtian Ma
첫째 줄에 \(N\)과 \(Q\)가 주어진다.
둘째 줄에 \(c_1, c_2, c_3 \dots c_N\) (\(1 \leq c_i \leq 10^6\))이 주어진다.
셋째 줄에 \(t_1, t_2, t_3 \dots t_N\) (\(1 \leq t_i \leq 10^6\))이 주어진다.
다음 \(Q\)개의 줄에 각각 두 정수 \(V\) (\(1 \leq V \leq N\))와 \(S\) (\(1 \leq S \leq 10^6\))가 주어진다.
\(Q\)개의 질의 각각에 대해 YES 또는 NO를 새 줄에 출력한다.
5 5
3 5 7 9 12
4 2 3 3 8
1 5
1 6
3 3
4 2
5 1YES
NO
YES
YES
NOFor the first query, Bessie will visit the farms at time \(t = [9, 7, 8, 8, 13]\),
so she will only get to visit farm \(4\) on time before FJ closes the farm.
For the second query, Bessie will not be able to visit any of the farms on time.
For the third query, Bessie will visit farms \(3, 4, 5\) on time.
For the fourth and fifth queries, Bessie will be able to visit all but the first
farm on time.
riseoj 작성
출처 올림피아드 > USACO > 2023-2024 > February > Bronze