Submission #23459626

---

Source Code Expand

def binary_search(data, value):
    left = 0
    right = len(data) - 1
    while left <= right:
        mid = (left + right) // 2
        if data[mid - 1] < value and value <= data[mid]:
            return mid
        elif data[mid] < value:
            left = mid + 1
        elif value <= data[mid - 1]:
            right = mid - 1
    return -1

n, q = map(int, input().split())
a = list(map(int, input().split()))
a = [0] + a
c = [0]

for i in range(1, n + 1):
    c += [c[i - 1] + a[i] - a[i - 1] - 1]

for _ in range(q):
    k = int(input())
    if c[n] < k:
        res = a[n] + k - c[n]
    else:
        idx = binary_search(c, k)
        res = a[idx] - 1 + k - c[idx]
    print(res)

Submission Info

Judge Result