Scuza (Codeforces 1742E)
Tags: Greedy, binary search

Timur has a stairway with $$$n$$$ steps. The $$$i$$$-th step is $$$a_i$$$ meters higher than its predecessor. The first step is $$$a_1$$$ meters higher than the ground, and the ground starts at $$$0$$$ meters.   The stairs for the first test case. Timur has $$$q$$$ questions, each denoted by an integer $$$k_1, \dots, k_q$$$. For each question $$$k_i$$$, you have to print the maximum possible height Timur can achieve by climbing the steps if his legs are of length $$$k_i$$$. Timur can only climb the $$$j$$$-th step if his legs are of length at least $$$a_j$$$. In other words, $$$k_i \geq a_j$$$ for each step $$$j$$$ climbed.Note that you should answer each question independently.

Input: The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.The first line of each test case contains two integers $$$n, q$$$ ($$$1 \leq n, q \leq 2\cdot10^5$$$) — the number of steps and the number of questions, respectively.The second line of each test case contains $$$n$$$ integers ($$$1 \leq a_i \leq 10^9$$$) — the height of the steps.The third line of each test case contains $$$q$$$ integers ($$$0 \leq k_i \leq 10^9$$$) — the numbers for each question.It is guaranteed that the sum of $$$n$$$ does not exceed $$$2\cdot10^5$$$, and the sum of $$$q$$$ does not exceed $$$2\cdot10^5$$$.

Output: For each test case, output a single line containing $$$q$$$ integers, the answer for each question.Please note, that the answer for some questions won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

Note: Consider the first test case, pictured in the statement.   If Timur's legs have length $$$1$$$, then he can only climb stair $$$1$$$, so the highest he can reach is $$$1$$$ meter.  If Timur's legs have length $$$2$$$ or $$$4$$$, then he can only climb stairs $$$1$$$, $$$2$$$, and $$$3$$$, so the highest he can reach is $$$1+2+1=4$$$ meters.  If Timur's legs have length $$$9$$$ or $$$10$$$, then he can climb the whole staircase, so the highest he can reach is $$$1+2+1+5=9$$$ meters.  In the first question of the second test case, Timur has no legs, so he cannot go up even a single step. :(

Sample Inputs:
3
4 5
1 2 1 5
1 2 4 9 10
2 2
1 1
0 1
3 1
1000000000 1000000000 1000000000
1000000000

Sample Outputs:
1 4 4 9 9 
0 2 
3000000000

Solution (Python):
from bisect import bisect
t = int(input())
for _ in range(t):
    (n, q) = map(int, input().split())
    input_numbers = list(map(int, input().split()))
    arr = [0] + input_numbers + [1000000000.0 + 7]
    b = list(map(int, input().split()))
    _arr = arr.copy()
    for i in range(1, n + 2):
        _arr[i] += _arr[i - 1]
        arr[i] = max(arr[i], arr[i - 1])
    for i in range(q):
        b[i] = _arr[bisect(arr, b[i]) - 1]
    print(' '.join(map(str, b)))

Solution (Python):
for _ in range(int(input())):
    (n, q) = map(int, input().split())
    A = list(map(int, input().split()))
    Q = list(map(int, input().split()))
    sortQ = sorted(Q)
    height = 0
    i = 0
    dico = {}
    for k in sortQ:
        while i < n and A[i] <= k:
            height += A[i]
            i += 1
        dico[k] = height
    print(' '.join([str(dico[p]) for p in Q]))

Solution (Python):
from collections import defaultdict
import bisect
k = int(input())
for _ in range(k):
    (n, m) = list(map(int, input().split()))
    arr = list(map(int, input().split()))
    query = list(map(int, input().split()))
    presum = [0]
    maxarr = [0]
    for h in arr:
        presum.append(presum[-1] + h)
        maxarr.append(max(maxarr[-1], h))
    ans = []
    for q in query:
        pos = bisect.bisect_right(maxarr, q)
        ans.append(str(presum[pos - 1]) + ' ')
    print(''.join(ans))