Problem p04017 (python)

Fixed submission:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = I()
    x = LI()
    l = I()
    k = int(math.log(n,2))
    f = [[i for j in range(k+1)] for i in range(n)]
    for i in range(n-1):
        j = bisect.bisect_left(x,x[i]+l)
        if j < n:
            if x[j] > x[i]+l:
                f[i][0] = j-1
            else:
                f[i][0] = j
        else:
            f[i][0] = j-1
    po2 = [1]*(k+1)
    for i in range(k):
        po2[i+1] = po2[i]*2
    for j in range(k):
        for i in range(n):
            f[i][j+1] = f[f[i][j]][j]
    q = I()
    for i in range(q):
        a,b = LI()
        a,b = [min(a,b)-1, max(a,b)-1]
        ans = 0
        while a < b:
            i = bisect.bisect_left(f[a],b)
            ans += po2[max(0,i-1)]
            a = f[a][max(0,i-1)]
        print(ans)

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    x = LI()
    f = [[] for i in range(n)]
    l = I()
    for i in range(n):
        xi = x[i]
        j = bisect.bisect_right(x,l+xi)-1
        f[i].append(j)
    h = int(math.log(n,2))+1
    for j in range(h-1):
        for i in range(n):
            f[i].append(f[f[i][j]][j])
    q = I()
    for _ in range(q):
        a,b = LI()
        a -= 1
        b -= 1
        if b < a:
            a,b = b,a
        ans = 0
        while a != b:
            i = bisect.bisect_left(f[a],b)
            ans += 1<<i
            a = f[a][i]
        print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = I()
    x = LI()
    l = I()
    k = int(math.log(n,2))
    f = [[i for j in range(k+1)] for i in range(n)]
    for i in range(n-1):
        j = bisect.bisect_left(x,x[i]+l)
        if j < n:
            if x[j] > x[i]+l:
                f[i][0] = j-1
            else:
                f[i][0] = j
        else:
            f[i][0] = j-1
    po2 = [1]*(k+1)
    for i in range(k):
        po2[i+1] = po2[i]*2
    for j in range(k):
        for i in range(n):
            f[i][j+1] = f[f[i][j]][j]
    q = I()
    for i in range(q):
        a,b = LI()
        a,b = [min(a,b)-1, max(a,b)-1]
        ans = 0
        while a < b:
            i = bisect.bisect_left(f[a],b)
            ans += po2[i]
            if f[a][i] == b:
                break
            a = f[a][i-1]
        print(ans)

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = I()
    x = LI()
    l = I()
    k = int(math.log(n,2))
    f = [[i for j in range(k+1)] for i in range(n)]
    for i in range(n-1):
        j = bisect.bisect_left(x,x[i]+l)
        if j < n:
            if x[j] > x[i]+l:
                f[i][0] = j-1
            else:
                f[i][0] = j
        else:
            f[i][0] = j-1
    po2 = [1]*(k+1)
    for i in range(k):
        po2[i+1] = po2[i]*2
    for j in range(k):
        for i in range(n):
            f[i][j+1] = f[f[i][j]][j]
    q = I()
    for i in range(q):
        a,b = LI()
        a,b = [min(a,b)-1, max(a,b)-1]
        ans = 0
        while 1:
            i = bisect.bisect_left(f[a],b)
            if f[f[a][i-1]][0] < b < f[a][i] or f[a][i] == b:
                ans += po2[i]
                break
            ans += po2[i-1]
            a = f[a][i-1]
        print(ans)

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = I()
    x = LI()
    l = I()
    k = int(math.log(n,2))
    f = [[i for j in range(k+1)] for i in range(n)]
    for i in range(n-1):
        j = bisect.bisect_left(x,x[i]+l)
        if j < n:
            if x[j] > x[i]+l:
                f[i][0] = j-1
            else:
                f[i][0] = j
        else:
            f[i][0] = j-1
    po2 = [1]*(k+1)
    for i in range(k):
        po2[i+1] = po2[i]*2
    for j in range(k):
        for i in range(n):
            f[i][j+1] = f[f[i][j]][j]
    q = I()
    for i in range(q):
        a,b = LI()
        a,b = [min(a,b)-1, max(a,b)-1]
        ans = 0
        while 1:
            i = bisect.bisect_left(f[a],b)
            if f[a][i] == b:
                ans += po2[i]
                break
            ans += po2[i-1]
            a = f[a][i-1]
        print(ans)

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()

Buggy submission (verdict: Runtime Error):
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n = I()
    x = LI()
    l = I()
    k = int(math.log(n,2))
    f = [[i for j in range(k+1)] for i in range(n)]
    for i in range(n-1):
        j = bisect.bisect_left(x,x[i]+l)
        if j < n:
            if x[j] > x[i]+l:
                f[i][0] = j-1
            else:
                f[i][0] = j
        else:
            f[i][0] = j-1
    po2 = [1]*(k+1)
    for i in range(k):
        po2[i+1] = po2[i]*2
    for j in range(1,k+1):
        for i in range(n):
            f[i][j] = f[f[i][j-1]][j-1]
    q = I()
    for i in range(q):
        a,b = LI()
        a,b = [min(a,b)-1, max(a,b)-1]
        i = 0
        while x[f[a][i]] < x[b]:
            i += 1
        if x[f[a][i]] == x[b]:
            print(po2[i])
        else:
            ans = po2[i]
            s = f[f[a][i-1]][0]
            g = f[b][0]
            while s < g:
                s = f[s][0]
                ans += 1
            print(ans)

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    C()