Formation
Contest: Hello 2025
Difficulty rating: 3300
Tags: binary search, data structures, dp, sortings, two pointers

One day, the teachers of "T-generation" decided to instill discipline in the pupils, so they lined them up and made them calculate in order. There are a total of $$$n$$$ pupils, the height of the $$$i$$$-th pupil in line is $$$a_i$$$.

The line is comfortable, if for each $$$i$$$ from $$$1$$$ to $$$n - 1$$$, the following condition holds: $$$a_i \cdot 2 \ge a_{i + 1}$$$. Initially, the line is comfortable.

The teachers do not like that the maximum height in the line is too small, so they want to feed the pupils pizza. You know that when a pupil eats one pizza, their height increases by $$$1$$$. One pizza can only be eaten by only one pupil, but each pupil can eat an unlimited number of pizzas. It is important that after all the pupils have eaten their pizzas, the line is comfortable.

The teachers have $$$q$$$ options for how many pizzas they will order. For each option $$$k_i$$$, answer the question: what is the maximum height $$$\max(a_1, a_2, \ldots, a_n)$$$ that can be achieved if the pupils eat at most $$$k_i$$$ pizzas.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each set of test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 5 \cdot 10^4$$$) — the number of pupils and the number of options for how many pizzas the teachers will order.

The second line of each set of test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the heights of the pupils.It is guaranteed that initially, the line is comfortable.

Each of the following $$$q$$$ lines of each set of input data contains one integer $$$k_i$$$ ($$$1 \le k_i \le 10^9$$$) — the next limit for how many pizzas the pupils can eat.

It is guaranteed that the sum of the values of $$$n$$$ across all sets of input data does not exceed $$$5 \cdot 10^4$$$.

It is guaranteed that the sum of the values of $$$q$$$ across all sets of input data does not exceed $$$5 \cdot 10^4$$$.

Output format:
For each test case, for each limit for how many pizzas the pupils can eat, output the maximum value $$$\max(a_1, a_2, \ldots, a_n)$$$ that can be achieved while ensuring that the line is comfortable.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first query of the first set of input data, you can first give $$$3$$$ pizzas to the first pupil, and then give $$$6$$$ pizzas to the second pupil, making the final array $$$[13, 26]$$$ (the line is comfortable since $$$13 \cdot 2 \ge 26$$$), and the maximum element in it is $$$26$$$.

Example input:
3
2 1
10 20
10
6 7
3 1 2 4 5 6
1
2
4
8
16
32
64
10 4
1 2 4 8 16 32 64 128 256 512
10
100
1000
10000

Example output:
26
7 8 10 12 19 35 67
513 560 1011 10001

Editorial:
Hint 1: how much does a single index affect those before him?
Hint 2: try looking at the formula for making an index a maximum differently
Hint 3: do you need to answer all queries online?
Hint 4: do you need to consider all indexes?
Solution: Let's fix the index that we want our maximum to be on — let it be $$$i$$$. Then, due to $$$k_i$$$ being $$$\le 10^9$$$ in each test case, and every number in our array $$$a$$$ also being $$$\le 10^9$$$, we do not need to consider any indexes before $$$i - 30$$$ — they are also valid as they were part of the previous good array, and we do not need to make them bigger as $$$2^{31} \ge 2 * 10^9$$$.
Now let's try doing binary search on the answer for each query (let our current query be with the number $$$M$$$). When we fix our possible answer as $$$X$$$ at index $$$i$$$, what does that mean? It means that we need $$$a_i \ge X, a_{i-1} \ge \lceil{\frac{X}{2}} \rceil$$$, and so on, calculating every index through the next one $$$(i$$$ from $$$i + 1)$$$. Let us call this auxiliary array $$$c$$$ $$$( c_0 = X, c_i = \lceil\frac{c_{i - 1}}{2} \rceil)$$$. So, if we need to change exactly $$$k$$$ indexes before $$$i$$$ ($$$i$$$, $$$i - 1$$$, ..., $$$i - k$$$) , our condition for checking whether we could do that is as followed:
$$$1$$$. $$$a_{i - j} \le c_j$$$ for each $$$0 \le j \le k$$$
$$$2$$$. $$$\sum_{j = 0}^{k} c_j - a_{i - j} \le M$$$.
Now, we can see that for each fixed $$$k$$$ from $$$0$$$ to $$$log MAX = 30$$$, we should choose such an index $$$i$$$, that its previous indexes satisfy condition $$$1$$$ from above, and $$$\sum_{j = 0}^{k} a_{i - j}$$$ is minimal.
Let's consider solving this via scanline. For each index $$$i$$$ and each $$$k$$$ from $$$0$$$ to $$$30$$$, let's consider the possible values of $$$M$$$ such that if we want our maximum to be on index $$$i$$$, it will affect exactly $$$(a_i, a_{i - 1}, \ldots, a_{i - k})$$$. We can notice that such values form a segment $$$[L_{ik}, R_{ik}]$$$, which is possiblyinvalid $$$(L_{ik} > R_{ik})$$$. We can find these segments in $$$O(N log MAX)$$$.
Now let's go through the request offline in ascending order, maintaining currently active indexes. We maintain $$$log MAX + 1$$$ multisets with the minimum possible sums on valid segments of each length, and update them on each opening/closing of a segment $$$($$$ this is done in $$$O(N log ^ 2 MAX) )$$$. On each request, we do binary search on the answer, and check all $$$log MAX$$$ length candidates.