맛있는 사과

면접 대비

시간 제한2초메모리 제한2048 MB

요약
각 질문 p에 대해 맛이 p 이상인 사과 중 크기가 가장 큰 사과가 몇 개인지 구한다.
난이도

보통10점 중 6점

유형
정렬, 이분 탐색, 누적 합, 배열
정답자
아직 제출이 없습니다

문제

11번부터 NN번까지 NN개의 사과가 있습니다. ii번 사과의 맛은 t_it\_i, ii번 사과의 크기는 s_is\_i입니다.

여러분은 QQ개의 질문에 답해야 합니다. 질문으로 정수 pp가 주어지면, 맛 t_it\_i가 pp 이상인 사과 중 크기 s_is\_i가 가장 큰 사과의 개수를 출력해야 합니다. 조건에 해당하는 사과가 존재하지 않을 경우, 0을 출력합니다.

입력

첫 번째 줄에 사과의 개수 NN과 질문의 개수 QQ가 공백으로 구분되어 주어집니다.

두 번째 줄에 각 사과의 맛을 나타내는 정수 t_1t\_1, t_2t\_2, …\dots, t_Nt\_N이 공백으로 구분되어 주어집니다.

세 번째 줄에 각 사과의 크기를 나타내는 정수 s_1s\_1, s_2s\_2, …\dots, s_Ns\_N이 공백으로 구분되어 주어집니다.

다음 QQ개 줄에 걸쳐 질문으로 정수 pp가 한 줄에 하나씩 주어집니다.

출력

QQ개의 줄에 걸쳐 각 pp마다 맛 t_it\_i가 pp 이상인 사과 중 크기 s_is\_i가 가장 큰 사과의 개수를 한 줄에 하나씩 순서대로 출력합니다.

제한

  • 1≤N,Q≤200,0001 \le N, Q \le 200\\, 000
  • 1≤t_i,s_i≤1,000,000,0001 \le t\_i, s\_i \le 1\\, 000\\, 000\\, 000
  • 1≤p≤1,000,000,0001 \le p \le 1\\, 000\\, 000\\, 000

예제1

  1. 예제 1

    입력
    5 5
    1 3 2 4 5
    3 2 3 2 1
    1
    2
    3
    4
    5
    
    예상 출력
    2
    1
    2
    1
    1