아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

플래피 버드 스코어링

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

요약
각 새 크기마다 틈새가 새보다 좁은 첫 장애물을 찾는다. 그 지점에서 점수가 멈추기 때문이다.
난이도

보통10점 중 5점

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

문제

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

하나의 장애물을 피할 때마다 11점씩 점수를 얻게 된다. 게임에는 총 NN개의 장애물이 존재하고, ii번째 장애물은 두 개의 장애물로 표현된다. 상단 장애물 끝 지점의 위치는 A_iA\_i로 나타내어지고, 하단 장애물 끝 지점의 위치는 B_iB\_i로 나타내어진다.

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

여러 종류의 플래피 버드가 각 게임마다 주어질 때, 해당 플래피 버드를 가지고 몇 점까지 획득할 수 있는지 구하려고 한다.

세정이의 게임 스코어를 구해 출력해보자.

입력

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

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

세 번째 줄에는 하단 장애물의 위치 B_iB\_i가 공백으로 구분되어 주어진다. (−109≤B_i≤109)(-10^9 \le B\_i \le 10^9) (이때, 주어지는 입력은 B_i≤A_iB\_i \le A\_i임이 보장된다.)

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

다섯 번째 줄에는 각 플래피 버드의 크기 w_iw\_i가 주어진다. (1≤w_i≤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