ページが読み込まれませんか？ こちらをクリックすると直るかもしれません。
Placeholder

#2483

[초등부] 2025 KOI 1차대회 대비 모의고사 (1주차)

부지런한 영업사원
サブタスク
1秒 1024MB

問題

한글이는 N개의 가게를 운영하고 있다 (1 \leq N \leq 2 \times 10^5).

  • 각 가게는 1번부터 N번까지 번호가 붙어 있고, 각 i번 가게는 c_i시간에 운영을 종료한다.

영업사원 정올이는 시간 S에 일어나서 가능한 많은 가게를 방문하고 싶어 한다.

  • 그는 i번 가게를 t_i + S시간에 방문할 계획이다. 정올이는 가게가 닫히기 전에 가게에 도달해야만 방문할 수 있다.

정올이는 Q개의 쿼리를 가지고 있다 (1 \leq Q \leq 2 \times 10^5). 각 쿼리에서 두 개의 정수 S와 V를 주어준다.

  • 각 쿼리에 대해 정올이가 시간 S에 일어나서 방문 할 수 있는 가게의 후보가 최소한 V개의 이상인지 출력하라.


入力

첫 번째 줄에는 N과 Q가 주어진다.

두 번째 줄에는 가게 1부터 N까지의 닫히는 시간 c_1, c_2, c_3, \dots, c_N이 주어진다 (1 \leq c_i \leq 10^6).

세 번째 줄에는 가게 1부터 N까지의 방문 시간 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)가 주어진다.


出力

각 쿼리에 대해 정올이가 시간 S에 일어나서 방문 할 수 있는 가게의 후보가 최소한 V개의 이상이면 "YES"를 출력하고, 그렇지 않으면 "NO"를 출력한다.


部分問題

番号 点数 条件
#133点

N,Q≤10^3

#233点

c_i,t_i≤20

#334点

추가 제약 조건 없음


例題 

5 5
3 5 7 9 12
4 2 3 3 8
1 5
1 6
3 3
4 2
5 1
YES
NO
YES
YES
NO

첫 번째 쿼리에서, 정올이는 t=[9,7,8,8,13]에서 가게들을 방문할 수 있다. 그러므로 가게 4만 방문할 수 있다.

두 번째 쿼리에서, 정올이는 어느 가게도 제 시간에 방문할 수 없다.

세 번째 쿼리에서, 정올이는 가게 3, 4, 5를 제 시간에 방문할 수 있다.

네 번째와 다섯 번째 쿼리에서, 정올이는 가게 1을 제외한 나머지 가게들을 제 시간에 방문할 수 있다.

ログインしないとコードを書けません。