만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

플래피 버드 스코어링

면접 대비

시간 제한1초메모리 제한512 MB

요약
장애물마다 위아래 사이 틈 A_i - B_i를 구하고, 새 크기 w마다 틈이 w보다 좁은 장애물을 만나기 전까지 통과한 개수를 구합니다.
난이도

쉬움10점 중 3점

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

문제

플래피 버드는 장애물을 피해 최대한 멀리까지 도달하는 게임이다.

장애물을 하나 피할 때마다 11점을 얻는다. 게임에는 장애물이 총 NN개 있고, ii번째 장애물은 두 개의 장애물로 이루어진다. 상단 장애물 끝 지점의 위치는 AiA_i이고, 하단 장애물 끝 지점의 위치는 BiB_i이다.

플래피 버드 고수 세정이는 장애물이 어떤 식으로 주어지든 플래피 버드를 조작해 피할 수 있다. (단, 플래피 버드의 크기가 장애물의 틈새보다 클 경우에는 세정이도 장애물을 피하지 못한다.) 즉, 플래피 버드의 크기 ww가 장애물의 틈새보다 크면 그 장애물을 피하지 못한다. 장애물을 피하지 못하면 게임이 바로 끝난다.

게임마다 서로 다른 플래피 버드가 주어진다. 각 플래피 버드로 몇 점까지 얻을 수 있는지 구한다.

세정이의 게임 스코어를 구해 출력한다.

입력

첫 번째 줄에 장애물의 개수 NN이 주어진다. (1≤N≤250 000)(1 \le N \le 250\ 000)

두 번째 줄에 상단 장애물의 위치 AiA_i가 공백으로 구분되어 주어진다. (−109≤Ai≤109)(-10^9 \le A_i \le 10^9)

세 번째 줄에 하단 장애물의 위치 BiB_i가 공백으로 구분되어 주어진다. (−109≤Bi≤109)(-10^9 \le B_i \le 10^9) (입력은 Bi≤AiB_i \le A_i임이 보장된다.)

네 번째 줄에 플레이할 플래피 버드의 개수 QQ가 주어진다. (1≤Q≤250,000)(1 \le Q \le 250,000)

다섯 번째 줄에 각 플래피 버드의 크기 wiw_i가 주어진다. (1≤wi≤109)(1 \le w_i \le 10^9)

출력

각 플래피 버드마다 세정이가 얻을 수 있는 최대 게임 스코어를 한 줄에 하나씩 출력한다.

예제1

  1. 예제 1

    입력
    7
10 5 7 7 8 9 10
1 -1 2 -1 5 2 9
4
3 7 5 1
    예상 출력
    6
1
4
7