Problem p03158 (python)

Fixed submission:
import sys
input = sys.stdin.readline
def calc(x):
    l, r = 0, (N+1)//2
    while r - l > 1:
        m = (l+r) // 2
        if A[m] + A[2*m] >= 2 * x:
            l = m
        else:
            r = m
    return l
    
N, Q = map(int, input().split())
A = [int(a) for a in input().split()][::-1]
B = [A[0]] + [0] * (N-1)
for i in range(1, N):
    B[i] = B[i-1] + A[i]
C = [A[0]] + [0] * (N-1)
for i in range(2, N, 2):
    C[i] = C[i-2] + A[i]
C[-1] += C[-2]
for _ in range(Q):
    x = int(input())
    c = calc(x)
    print(B[c] + (C[-1] - C[2*c] if c*2<=N else 0))

Buggy submission (verdict: Runtime Error):
import bisect
N, Q = map(int, input().split())
A = [int(a) for a in input().split()]

def chk(x, l, m, r):
    if x >= A[-2]:
        return 1
    elif x <= A[0]:
        return (N+1)//2
    rr = m % 2
    xl = x - m//2 - rr
    xr = x + m//2
    
    ll = bisect.bisect_left(A, xl)
    rr = bisect.bisect_left(A, xr+1)-1
    # print(x, l, m, r, ll, rr, N)
    if rr - ll + 1 < N - rr - 2:
        return chk(x, m, (m+r)//2, r)
    elif rr - ll + 1 > N - 1 - rr:
        return chk(x, l, (l+m)//2, m)
    else:
        return max(N - rr - 1, 1)
    
    
Y = [0] * (N+1)
for i in range(1, N+1):
    Y[i] = Y[i-1] + A[-i]

Z = [0] * ((N+3)//2)
for i in range((N+1)//2):
    if ((1+N)%2)+2*i<N:
        Z[i+1] = Z[i] + A[((1+N)%2)+2*i]

# print(Y)
# print(Z)
for q in range(Q):
    x = int(input())
    t = chk(x, 0, A[-1]//2, A[-1])
    # print(t)
    print(Y[t]+Z[(N+1)//2-t])

Buggy submission (verdict: Runtime Error):
import bisect
N, Q = map(int, input().split())
A = [int(a) for a in input().split()]

def chk(x, l, m, r):
    if x >= A[-2]:
        return 1
    elif x <= A[0]:
        return (N+1)//2
    rr = m % 2
    xl = x - m//2 - rr
    xr = x + m//2
    
    ll = bisect.bisect_left(A, xl)
    rr = bisect.bisect_left(A, xr+1)-1
    # print(x, l, m, r, ll, rr, N)
    if rr - ll + 1 < N - rr - 2:
        if m == (m+r)//2:
            print(1/0)
        return chk(x, m, (m+r)//2, r)
    elif rr - ll + 1 > N - 1 - rr:
        if l == (l+m)//2:
            print(1/0)
        return chk(x, l, (l+m)//2, m)
    else:
        return max(N - rr - 1, 1)
    
    
Y = [0] * (N+1)
for i in range(1, N+1):
    Y[i] = Y[i-1] + A[-i]

Z = [0] * ((N+3)//2)
for i in range((N+1)//2):
    if ((1+N)%2)+2*i<N:
        Z[i+1] = Z[i] + A[((1+N)%2)+2*i]

# print(Y)
# print(Z)
for q in range(Q):
    x = int(input())
    t = chk(x, 0, A[-1]//2, A[-1])
    # print(t)
    print(Y[t]+Z[(N+1)//2-t])

Buggy submission (verdict: Runtime Error):
import bisect
N, Q = map(int, input().split())
A = [int(a) for a in input().split()]

def chk(x, l, m, r):
    if x >= A[-2]:
        return 1
    rr = m % 2
    xl = x - m//2 - rr
    xr = x + m//2
    
    ll = bisect.bisect_left(A, xl)
    rr = bisect.bisect_left(A, xr+1)-1
    # print(x, l, m, r, ll, rr, N)
    if rr - ll + 1 < N - rr - 2:
        if m == (m+r)//2:
            print(1/0)
        return chk(x, m, (m+r)//2, r)
    elif rr - ll + 1 > N - 1 - rr:
        if l == (l+m)//2:
            print(1/0)
        return chk(x, l, (l+m)//2, m)
    else:
        return N - rr - 1
    
    
Y = [0] * (N+1)
for i in range(1, N+1):
    Y[i] = Y[i-1] + A[-i]

Z = [0] * ((N+3)//2)
for i in range((N+1)//2):
    if ((1+N)%2)+2*i<N:
        Z[i+1] = Z[i] + A[((1+N)%2)+2*i]

# print(Y)
# print(Z)
for q in range(Q):
    x = int(input())
    t = chk(x, 0, A[-1]//2, A[-1])
    # print(t)
    print(Y[t]+Z[(N+1)//2-t])

Buggy submission (verdict: Runtime Error):
import bisect
N, Q = map(int, input().split())
A = [int(a) for a in input().split()]

def chk(x, l, m, r):
    rr = m % 2
    xl = x - m//2 - rr
    xr = x + m//2
    
    ll = bisect.bisect_left(A, xl)
    rr = bisect.bisect_left(A, xr+1)-1
    print(x, l, m, r, ll, rr, N)
    if rr - ll + 1 < N - rr - 2:
        if m == (m+r)//2:
            print(1/0)
        return chk(x, m, (m+r)//2, r)
    elif rr - ll + 1 > N - 1 - rr:
        if l == (l+m)//2:
            print(1/0)
        return chk(x, l, (l+m)//2, m)
    else:
        return (m+1)//2
    
    
Y = [0] * N
for i in range(1, N):
    Y[i] = Y[i-1] + A[-i-1]

Z = [0] * N
for i in range(1, N):
    Z[i] = Z[i-1] + A[((1+N)%2)::2]

for q in range(Q):
    x = int(input())
    t = chk(x, 0, A[-1]//2, A[-1])
    print(Y[t]+Z[N-t])