페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8261
서브태스크
다국어

중앙값 힙 4초 1024MB

문제

Farmer John은 1 \le N < 2\cdot10^5개의 노드를 가진 이진 트리를 가지고 있다. 노드는 1부터 N까지 번호가 매겨져 있으며, N은 항상 홀수이다.

모든 i > 1에 대해, 노드 i의 부모 노드는 \lfloor i/2 \rfloor 이다. 각 노드는 초기 정수 값 a_i 와, 이 초기 값을 다른 정수 값으로 변경하는 데 드는 비용 c_i 를 가진다. (0 \le a_i, c_i \le 10^9)

Federal Bovine Intermediary (FBI)는 이 트리에서 근사 중앙값(approximate median) 을 찾는 작업을 FJ에게 맡겼다. 이를 위해 FJ는 다음과 같은 알고리즘을 고안했다.

  1. 마지막 노드 N부터 역순으로 탐색한다.

  2. 현재 노드가 자신의 두 자식과 함께 중앙값이 아니라면, 현재 노드와 중앙값이 되는 자식 노드의 값을 교환한다.

  3. 이 과정을 반복하면, 최종적으로 루트 노드(노드 1)의 값이 근사 중앙값 이 된다.

FBI는 FJ에게 1 \le Q \le 2\cdot10^5 개의 독립적인 질의를 제공했다. 각 질의는 목표 값 m (0 \le m \le 10^9) 로 구성된다.

각 질의에 대해, FJ는 일부 노드의 초기 값을 변경한 후 근사 중앙값 알고리즘 을 실행한다.
이때, 알고리즘 실행 후 루트 노드의 값이 m 이 되도록 하는 최소 비용을 구하라.


입력

입력의 첫 번째 줄에는 N이 주어진다.

다음 N개의 줄에는 각각 두 개의 정수 a_i 와 c_i 가 주어진다.

그다음 줄에는 Q가 주어진다.

다음 Q개의 줄에는 각각 목표 값 m이 주어진다.


출력

출력은 Q개의 줄에 대해 각 목표 값 m에 대한 최소 가능한 총 비용을 출력한다.


부분문제

번호 점수 조건
#120점

N,Q≤50

#230점

N,Q≤1000

#350점

추가 제약 조건 없음


예제1

입력
5
1010000
301000
20100
5010
401
11
55
50
45
40
35
30
25
20
15
10
5
출력
111
101
101
100
100
100
100
0
11
11
111

근사 중앙값을 40으로 만들기 위해, FJ는 노드 3의 값을 60으로 변경할 수 있다. 이 경우 비용은 c_3 = 100이다.

근사 중앙값을 45로 만들기 위해, FJ는 노드 3의 값을 60으로 변경하고, 노드 5의 값을 45로 변경해야 한다. 이 경우 총 비용은 c_3 + c_5 = 100 + 1 = 101 이다.


출처

USACO 2025 January Gold

역링크