| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 2048 MB | 36 | 20 | 19 | 54.286% |
Farmer John has a binary tree with $N$ nodes where the nodes are numbered from 1ドル$ to $N$ (1ドル \leq N < 2\cdot 10^5$ and $N$ is odd). For $i>1,ドル the parent of node $i$ is $\lfloor i/2\rfloor$. Each node has an initial integer value $a_i,ドル and a cost $c_i$ to change the initial value to any other integer value (0ドル\le a_i,c_i\le 10^9$).
He has been tasked by the Federal Bovine Intermediary (FBI) with finding an approximate median value within this tree, and has devised a clever algorithm to do so.
He starts at the last node $N$ and works his way backward. At every step of the algorithm, if a node would not be the median of it and its two children, he swaps the values of the current node and the child value that would be the median. At the end of this algorithm, the value at node 1ドル$ (the root) is the median approximation.
The FBI has also given Farmer John a list of $Q$ $(1 \leq Q \leq 2\cdot 10^5)$ independent queries each specified by a target value $m$ (0ドル\le m\le 10^9$). For each query, FJ will first change some of the node's initial values, and then execute the median approximation algorithm. For each query, determine the minimum possible total cost for FJ to make the output of the algorithm equal to $m$.
The first line of input contains $N$.
The next $N$ lines each contain two integers $a_i$ and $c_i$.
The next line contains $Q$.
The next $Q$ lines each contain a target value $m$.
Output $Q$ lines, the minimum possible total cost for each target value $m$.
5 10 10000 30 1000 20 100 50 10 40 1 11 55 50 45 40 35 30 25 20 15 10 5
111 101 101 100 100 100 100 0 11 11 111
To make the median approximation equal 40ドル,ドル FJ can change the value at node 3 to 60ドル$. This costs $c_3=100$.
To make the median approximation equal 45ドル,ドル FJ can change the value at node 3 to 60ドル$ and the value at node 5 to 45ドル$. This costs $c_3+c_5=100+1=101$.