Problem p04017 (python)

Fixed submission:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
L = int(sys.stdin.readline())
Q = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

N += 2
X = [X[0]] + X + [X[-1]]
X = np.array(X, dtype=int)
# dp[d][i]: i番のホテルから(2^d)日で何個右までいけるか
dp = np.zeros((N.bit_length() + 1, N), dtype=int)
dp[0] = np.searchsorted(X, X + L, side="right") - 1
for d in range(1, N.bit_length() + 1):
    dp[d] = dp[d - 1][dp[d - 1]]
dp = dp.tolist()


def solve(l, r):
    ret = 0
    d = len(dp) - 1
    while l + 1 < r:
        while d > 0 and dp[d][l] >= r:
            d -= 1
        ret += 1 << d
        l = dp[d][l]
    if l < r:
        ret += 1
    return ret


ans = []
for a, b in AB:
    ans.append(solve(min(a, b), max(a, b)))
print(*ans, sep='\n')

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
L = int(sys.stdin.readline())
Q = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

N += 2
X = [X[0]] + X + [X[-1]]
X = np.array(X, dtype=int)
# rdp[d][i]: i番のホテルから(2^d)日で何個右までいけるか
rdp = np.zeros((N.bit_length(), N), dtype=int)
rdp[0] = np.searchsorted(X, X + L, side='right') - np.arange(N) - 1
for d in range(1, N.bit_length()):
    rdp[d] = rdp[d - 1] + rdp[d - 1][np.arange(N) + rdp[d - 1]]

X = -X[::-1]
# ldp[d][i]: i番のホテルから(2^d)日で何個左までいけるか
ldp = np.zeros((N.bit_length(), N), dtype=int)
ldp[0] = np.searchsorted(X, X + L, side='right') - np.arange(N) - 1
for d in range(1, N.bit_length()):
    ldp[d] = ldp[d - 1] + ldp[d - 1][np.arange(N) + ldp[d - 1]]


# print(rdp)
# print(ldp)


def solver(l, r):
    ret = 0
    while l < r:
        d = np.searchsorted(rdp[:, l], r - l)
        if rdp[d, l] == r - l:
            ret += 2 ** d
            break
        if d > 0:
            d -= 1
        ret += 2 ** d
        l += rdp[d, l]
    return ret


def solvel(l, r):
    r = N - r - 1
    l = N - l - 1
    ret = 0
    while l < r:
        d = np.searchsorted(ldp[:, l], r - l)
        if ldp[d, l] == r - l:
            ret += 2 ** d
            break
        if d > 0:
            d -= 1
        ret += 2 ** d
        l += ldp[d, l]
    return ret


# print(np.searchsorted([1, 2, 5, 8, 9], 3))
# print(np.searchsorted([1, 2, 5, 8, 9], 4))
# print(np.searchsorted([1, 2, 5, 8, 9], 5))
# print(np.searchsorted([1, 2, 5, 8, 9], 6))
# print(np.searchsorted([1, 2, 5, 8, 9], 7))
# print()

for a, b in AB:
    if a < b:
        r = solver(a, b)
    else:
        r = solvel(a, b)
    print(r)

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
L = int(sys.stdin.readline())
Q = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

N += 1
X.append(X[-1])
X = np.array(X, dtype=int)
# rdp[d][i]: i番のホテルから(2^d)日で何個右までいけるか
rdp = np.zeros((N.bit_length(), N), dtype=int)
rdp[0] = np.searchsorted(X, X + L, side='right') - np.arange(N) - 1
for d in range(1, N.bit_length()):
    rdp[d] = rdp[d - 1] + rdp[d - 1][np.arange(N) + rdp[d - 1]]

X = -X[::-1]
# ldp[d][i]: i番のホテルから(2^d)日で何個左までいけるか
ldp = np.zeros((N.bit_length(), N), dtype=int)
ldp[0] = np.searchsorted(X, X + L, side='right') - np.arange(N) - 1
for d in range(1, N.bit_length()):
    ldp[d] = ldp[d - 1] + ldp[d - 1][np.arange(N) + ldp[d - 1]]


# print(rdp)
# print(ldp)


def solver(l, r):
    ret = 0
    while l < r:
        d = np.searchsorted(rdp[:, l], r - l)
        if rdp[d, l] == r - l:
            ret += 2 ** d
            break
        if d > 0:
            d -= 1
        ret += 2 ** d
        l += rdp[d, l]
    return ret


def solvel(l, r):
    r = N - r - 1
    l = N - l - 1
    ret = 0
    while l < r:
        d = np.searchsorted(ldp[:, l], r - l)
        if ldp[d, l] == r - l:
            ret += 2 ** d
            break
        if d > 0:
            d -= 1
        ret += 2 ** d
        l += ldp[d, l]
    return ret


# print(np.searchsorted([1, 2, 5, 8, 9], 3))
# print(np.searchsorted([1, 2, 5, 8, 9], 4))
# print(np.searchsorted([1, 2, 5, 8, 9], 5))
# print(np.searchsorted([1, 2, 5, 8, 9], 6))
# print(np.searchsorted([1, 2, 5, 8, 9], 7))
# print()

for a, b in AB:
    if a < b:
        r = solver(a - 1, b - 1)
    else:
        r = solvel(a - 1, b - 1)
    print(r)

Buggy submission (verdict: Runtime Error):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
X = list(map(int, sys.stdin.readline().split()))
L = int(sys.stdin.readline())
Q = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(Q)]

X = np.array(X, dtype=int)
# rdp[d][i]: i番のホテルから(2^d)日で何個右までいけるか
rdp = np.zeros((N.bit_length(), N), dtype=int)
rdp[0] = np.searchsorted(X, X + L, side='right') - np.arange(N) - 1
for d in range(1, N.bit_length()):
    rdp[d] = rdp[d - 1] + rdp[d - 1][np.arange(N) + rdp[d - 1]]

X = -X[::-1]
# ldp[d][i]: i番のホテルから(2^d)日で何個左までいけるか
ldp = np.zeros((N.bit_length(), N), dtype=int)
ldp[0] = np.searchsorted(X, X + L, side='right') - np.arange(N) - 1
for d in range(1, N.bit_length()):
    ldp[d] = ldp[d - 1] + ldp[d - 1][np.arange(N) + ldp[d - 1]]

# print(rdp)
# print(ldp)


def solver(l, r):
    ret = 0
    while l < r:
        d = np.searchsorted(rdp[:, l], r - l)
        if d > 0 and rdp[d, l] > r - l:
            d -= 1
        ret += 2 ** d
        l += rdp[d, l]
    return ret


def solvel(l, r):
    r = N - r - 1
    l = N - l - 1
    ret = 0
    while l < r:
        d = np.searchsorted(ldp[:, l], r - l)
        if d > 0 and ldp[d, l] > r - l:
            d -= 1
        ret += 2 ** d
        l += ldp[d, l]
    return ret


# print(np.searchsorted([1, 2, 5, 8, 9], 3))
# print(np.searchsorted([1, 2, 5, 8, 9], 4))
# print(np.searchsorted([1, 2, 5, 8, 9], 5))
# print(np.searchsorted([1, 2, 5, 8, 9], 6))
# print(np.searchsorted([1, 2, 5, 8, 9], 7))
# print()

for a, b in AB:
    if a < b:
        r = solver(a - 1, b - 1)
    else:
        r = solvel(a - 1, b - 1)
    print(r)