페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
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을 제외한 나머지 가게들을 제 시간에 방문할 수 있다.

로그인해야 코드를 작성할 수 있어요.