I have a fairly simple solution which passes all test cases. However, I fail to see how this question requires a search algorithm. The suggested topics included Binary Search but how do I incorporate binary search in this?

here is my DP solution.

n = int(input())
arr = list(map(int, input().split()))

q = int(input())
queries = list(map(int, input().split()))

count = [0]*4001
for i in arr:
    count[2000 + i] += 1
    
sum_num_right = []
sum_num_right.append(n)
for i in range(4000):
    sum_num_right.append(sum_num_right[i] - count[i])

sum_right = [0]*4001
for i in range(4001):
    sum_right[0] += count[i] * i
    
for i in range(1,4001):
    sum_right[i] = sum_right[i - 1] - sum_num_right[i]
    
sum_left = [0]*4001
for i in range(4000, -1, -1):
    sum_left[4000] += count[i] * (4000 - i)
    
for i in range(3999, -1, -1):
    sum_left[i] = sum_left[i + 1] - (n - sum_num_right[i + 1])
    
acc = 0
for i in queries:
    acc += i
    mid = 2000 - acc
    if mid < 4001 and mid >= 0:
        print(sum_right[mid] + sum_left[mid])
    elif mid < 0:
        print(sum_right[0] + n * abs(mid))
    else:
        print(sum_left[4000] + n * (mid - 4000))

the editorial says there is a O(logN) solution but that is impossible when you have to process Q sums. The complexity must have a variable for Q. I found a O(NlogN) + O(QlogN) algorithm but it only gets the test cases right up to #5 and times out for the last three cases. Is there a faster solution than O(NlogN) + O(QlogN)?

o(qlogn) is good enough. You need to consider the partial sum of the queries x instead of x and binary search for the index around which the sign is flipped after influence of this partial sum of x

I had fun solving this with C in 45 lines by calculating two constant sized tables before seeing any Q's and after that I'm just doing array lookups using the sum of all Q's so far. So my space is O(1) and time O(Q + N), and I did get rid of the 4001'ish Q multiplier in time as well which few people mentioned; I had that version at first too, but it failed the last two tests :)

For people stuck on test cases 6 and above, in java the results requires numbers above the MAX_VALUE of int. So it is necessary to change the returning array to long and change the "result" array in the main function to long[]. After I changed that i solved everything besides test case 12 which timed out which i eventually solved.