Problem p03158 (python)

Fixed submission:
def d_nearest_card_game(N, Q, A, X):
    # 最初は、高橋くんは数字の大きなカードを、青木くんはxに近いものから取っていく。
    # するといつか高橋くんが取りたいカードが青木くんに取られているような状況になるので、
    # そこからは2人で値の大きなものから順に取っていく。
    # そのため、2人で順に取っていく領域の広さ(N/2通り)がわかればいい。
    # N/2通りなのは、順に取っていくフェイズの前に2人がそれぞれ固まった領域の
    # カードを取るフェイズがN/2回あるため。
    # (Nが偶数のとき。奇数のときは両者が両端から取っていって
    # 最後に高橋くんが真ん中のカードを取ることがありうる)

    # これらの場合について、境界となるxの値を先に求めておけば、各クエリに対して
    # どの場合に当たるのかを高速に判定できる。

    # 境界となるxは青木くんがまとめて取ることになる領域の左右端の中央にある。
    # 数列のインデックスを右から0-basedで付けていくと、
    # 高橋くんがまとめて取っている領域は 0, 1, ..., i
    # 青木くんがまとめて取っている領域は i+1, i+2, ..., 2i+1
    # 境界となるxは (A[i+1]+A[2i+2])//2 + 1

    # iの値が分かったときに高橋くんの得点を求めるには、
    # Aの累積和とAの右から偶数番目だけ取る累積和を求めておけばいい。
    import bisect

    a = A[::-1]  # 「右から」はわかりづらいので逆にする
    # 累積和と偶数番目だけ足す累積和
    cumsum, evensum = [0] * (N + 1), [0] * (N + 1)
    for k, a_k in enumerate(a):
        cumsum[k + 1] = cumsum[k] + a_k
        evensum[k + 1] = evensum[k] + (a_k if k % 2 == 0 else 0)

    # 得点が変化するxの境界とそのときの得点
    threshold, threshold_score = [], []
    for k in range((N - 1) // 2):
        threshold.append((a[k + 1] + a[2 * k + 2]) // 2 + 1)
        threshold_score.append((cumsum[k + 1] - cumsum[0]) + (evensum[N] - evensum[2 * k + 2]))

    # Aを逆にしたので、もう一度逆にする
    threshold = threshold[::-1]
    threshold_score = threshold_score[::-1]

    ans = []
    for x in X:
        idx = bisect.bisect_right(threshold, x)
        if idx == 0:
            ans.append(cumsum[(N + 1) // 2] - cumsum[0])
        else:
            ans.append(threshold_score[idx - 1])
    ans = '\n'.join(map(str, ans))
    return ans

N, Q = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
X = [int(input()) for _ in range(Q)]
print(d_nearest_card_game(N, Q, A, X))

Buggy submission (verdict: Runtime Error):
def d_nearest_card_game(N, Q, A, X):
    # 最初は、高橋くんは数字の大きなカードを、青木くんはxに近いものから取っていく。
    # するといつか高橋くんが取りたいカードが青木くんに取られているような状況になるので、
    # そこからは2人で値の大きなものから順に取っていく。
    # そのため、2人で順に取っていく領域の広さ(N/2通り)がわかればいい。
    # N/2通りなのは、順に取っていくフェイズの前に2人がそれぞれ固まった領域の
    # カードを取るフェイズがN/2回あるため。
    # (Nが偶数のとき。奇数のときは両者が両端から取っていって
    # 最後に高橋くんが真ん中のカードを取ることがありうる)

    # これらの場合について、境界となるxの値を先に求めておけば、各クエリに対して
    # どの場合に当たるのかを高速に判定できる。

    # 境界となるxは青木くんがまとめて取ることになる領域の左右端の中央にある。
    # 数列のインデックスを右から0-basedで付けていくと、
    # 高橋くんがまとめて取っている領域は 0, 1, ..., i
    # 青木くんがまとめて取っている領域は i+1, i+2, ..., 2i+1
    # 境界となるxは (A[i+1]+A[2i+2])//2 + 1

    # iの値が分かったときに高橋くんの得点を求めるには、
    # Aの累積和とAの右から偶数番目だけ取る累積和を求めておけばいい。
    import bisect

    a = A[::-1]  # 「右から」はわかりづらいので逆にする
    # 累積和と偶数番目だけ足す累積和
    cumsum, evensum = [0] * (N + 1), [0] * (N + 1)
    for k, a_k in enumerate(a):
        cumsum[k + 1] = cumsum[k] + a_k
        evensum[k + 1] = evensum[k] + (a_k if k % 2 == 0 else 0)

    # 得点が変化するxの境界とそのときの得点
    threshold, threshold_score = [], []
    for k in range((N - 1) // 2):
        threshold.append((a[k + 1] + a[2 * k + 2]) // 2 + 1)
        threshold_score.append((cumsum[k + 1] - cumsum[0]) + (evensum[N] - evensum[2 * k + 2]))

    # Aを逆にしたので、もう一度逆にする
    threshold = threshold[::-1]
    threshold_score = threshold_score[::-1]

    ans = []
    for x in X:
        idx = bisect.bisect_right(threshold, x)
        if idx == 0:
            ans.append(cumsum[(N + 1) // 2] - cumsum[0])
        else:
            ans.append(threshold_score[idx - 1])
    ans = '\n'.join(map(str, ans))
    return ans

A = [int(i) for i in input().split()]
X = [int(input()) for _ in range(Q)]
print(d_nearest_card_game(N, Q, A, X))