Problem:


Score : 700 points

Problem Statement

N hotels are located on a straight line. The coordinate of the i-th hotel (1 \leq i \leq N) is x_i.

Tak the traveler has the following two personal principles:

He never travels a distance of more than L in a single day.

He never sleeps in the open. That is, he must stay at a hotel at the end of a day.

You are given Q queries. The j-th (1 \leq j \leq Q) query is described by two distinct integers a_j and b_j.
For each query, find the minimum number of days that Tak needs to travel from the a_j-th hotel to the b_j-th hotel following his principles.
It is guaranteed that he can always travel from the a_j-th hotel to the b_j-th hotel, in any given input.

Constraints

2 \leq N \leq 10^5

1 \leq L \leq 10^9

1 \leq Q \leq 10^5

1 \leq x_i < x_2 < ... < x_N \leq 10^9

x_{i+1} - x_i \leq L

1 \leq a_j,b_j \leq N

a_j \neq b_j

N,\,L,\,Q,\,x_i,\,a_j,\,b_j are integers.

Partial Score

200 points will be awarded for passing the test set satisfying N \leq 10^3 and Q \leq 10^3.

Input

The input is given from Standard Input in the following format:

N
x_1 x_2 ... x_N
L
Q
a_1 b_1
a_2 b_2
:
a_Q b_Q

Output

Print Q lines.
The j-th line (1 \leq j \leq Q) should contain the minimum number of days that Tak needs to travel from the a_j-th hotel to the b_j-th hotel.

Sample Input 1

9
1 3 6 13 15 18 19 29 31
10
4
1 8
7 3
6 7
8 5

Sample Output 1

4
2
1
2

For the 1-st query, he can travel from the 1-st hotel to the 8-th hotel in 4 days, as follows:

Day 1: Travel from the 1-st hotel to the 2-nd hotel. The distance traveled is 2.

Day 2: Travel from the 2-nd hotel to the 4-th hotel. The distance traveled is 10.

Day 3: Travel from the 4-th hotel to the 7-th hotel. The distance traveled is 6.

Day 4: Travel from the 7-th hotel to the 8-th hotel. The distance traveled is 10.



Sample input:
9
1 3 6 13 15 18 19 29 31
10
4
1 8
7 3
6 7
8 5


Sample output:
4
2
1
2

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def S_():
    return input()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()
#sys.setrecursionlimit(10**5)
input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=0

n=I()
m=n.bit_length()
x=LI()
L=I()
q=I()

r=[0]*n


for i in range(n):
    r[i]=bisect.bisect(x,x[i]+L)-1
    
nb=[r]
nx=[0]*n

for k in range(m):
    nx=[0]*n
    for i in range(n):
        nx[i]=r[r[i]]
    nb.append(nx)
    r=nx

for _ in range(q):
    a,b=LI_()
    if a>b:
        a,b=b,a
    
    t=0
    for p in range(m,-1,-1):
        if nb[p][a]<=b:
            t+=1<<p
            a=nb[p][a]
    
    print(t)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.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()
    L = I()
    q = I()
    p = [[] for i in range(n)]
    for i in range(n):
        xi = x[i]
        l = i
        r = n
        while r-l > 1:
            m = (l+r) >> 1
            xm = x[m]
            if xm-xi <= L:
                l = m
            else:
                r = m
        p[i].append(l)
    N = 20
    for j in range(N):
        for i in range(n):
            p[i].append(p[p[i][-1]][-1])
    for i in range(q):
        a,b = LI()
        a -= 1
        b -= 1
        a,b = min(a,b),max(a,b)
        ans = 0
        while a < b:
            j = bisect.bisect_left(p[a],b)
            ans += 1<<j
            a = p[a][j]
        print(ans)
    return

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.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()
    L = I()
    q = I()
    p = [[] for i in range(n)]
    for i in range(n):
        xi = x[i]
        l = i
        r = n
        while r-l > 1:
            m = (l+r) >> 1
            xm = x[m]
            if xm-xi <= L:
                l = m
            else:
                r = m
        p[i].append(l)
    N = 20
    for j in range(N):
        for i in range(n):
            p[i].append(p[p[i][-1]][-1])
    for i in range(q):
        a,b = LI()
        a -= 1
        b -= 1
        a,b = min(a,b),max(a,b)
        ans = 0
        while a < b:
            j = bisect.bisect_left(p[a],b)
            ans += 1<<j
            a = b
        print(ans)
    return

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

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
hotel_list = [ int(v) for v in input().split() ]
l = int(input())
ln = 16
hotel_list_2 = [ [ -1 for i in range(n) ]  for i in range(ln) ]

hotel_list_2[0] = [ bisect.bisect_right(hotel_list,v+l)-1  for v in hotel_list ]
for i in range(ln-1):
    hotel_list_2[i+1] = [ hotel_list_2[i][hotel_list_2[i][j]] for j in range(n) ]

def checkin(s,t):
    p, q = s, 0
    c = 1
    for i in range(ln):
        q = p
        p = hotel_list_2[i][s]
        if p == t:
            return c
        elif i == 0 and p > t:
            return c
        elif p > t:
            return c//2 + checkin(q,t)
        c *= 2

q = int(input())
for i in range(q):
    a, b = [ int(v)-1 for v in input().split() ]
    if a > b:
        a, b = b, a 
    print(checkin(a,b))

Submission status: Wrong Answer

Solution code:
n = int(input())
hot = list(map(int,input().split())) 
n_ = n.bit_length()
db = [[n-1]*(n)]
L = int(input())
r = 1
for i in range(n-1):
  while r < n-1 and hot[r+1]-hot[i] <= L:
    r += 1
  db[0][i] = r
for j in range(1,n_+1):
  new = [db[-1][db[-1][i]] for i in range(n)]
  db.append(new)
  if new[0] == n-1:
    break
n_ = len(db)

for x in db:
  print(x)
  
def query(s,t):
  dt = 0
  for j in range(n_-1,0,-1):
    if db[j][s] < t:
      dt += 2**j
      s = db[j][s]
  while s < t:
    dt += 1
    s = db[0][s]
  return dt 

q = int(input())
for _ in range(q):
  s,t = map(int,input().split())
  if t < s:
    s,t = t,s
  print(query(s-1,t-1))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
N = int(input())
x = list(map(int, input().split()))
L = int(input())
n = N.bit_length()
next_hotel = [[0]*n for _ in range(N)]
for i in range(N):
    index = bisect_right(x, x[i]+L)-1
    if index == i:
        next_hotel[i][0] = N
    else:
        next_hotel[i][0] = index
for i in range(1, n):
    for j in range(N):
        if next_hotel[j][i-1]<N:
            index = next_hotel[next_hotel[j][i-1]][i-1]
            if index == j:
                next_hotel[j][i] = N
            else:
                next_hotel[j][i] = index
        else:
            next_hotel[j][i] = N
def count(a, b):
    if a>b:
        a, b = b, a
    res = 0
    for i in range(n):
        if a >= b:
            return  res
        c = max(0, bisect_left(next_hotel[a], b)-1)
        a = next_hotel[a][c]
        res+=2**c
Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    print(count(a-1, b-1))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N = int(input())
x = list(map(int, input().split()))
L = int(input())
n = N.bit_length()
next_hotel = [[0]*n for _ in range(N)]
for i in range(N):
    index = bisect_right(x, x[i]+L)-1
    
    next_hotel[i][0] = index
for i in range(1, n):
    for j in range(N):
        next_hotel[j][i] = next_hotel[next_hotel[j][i-1]][i-1]
def count(a, b):
    if a>b:
        a, b = b, a
    res = 0
    for i in range(n):
        if a >= b:
            return  res
        c = max(bisect_right(next_hotel[a], b)-1, 0)
        a = next_hotel[a][c]
        res+=2**c
Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    print(count(a-1, b-1))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N = int(input())
x = list(map(int, input().split()))
L = int(input())
n = N.bit_length()
next_hotel = [[0]*n for _ in range(N)]
for i in range(N):
    index = bisect_right(x, x[i]+L)-1
    
    next_hotel[i][0] = index
for i in range(1, n):
    for j in range(N):
        next_hotel[j][i] = next_hotel[next_hotel[j][i-1]][i-1]
def count(a, b):
    if a>b:
        a, b = b, a
    res = 0
    for i in range(n):
        if a == b:
            return  res
        c = bisect_right(next_hotel[a], b)-1
        a = next_hotel[a][c]
        res+=2**c
Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    print(count(a-1, b-1))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

from bisect import bisect

n = int(input())
x = list(map(int, input().split()))
l = int(input())

m = 20
par = [[-1]*n for i in range(m)]

for i in range(n):
    j = bisect(x, x[i]+l)-1
    par[0][i] = j

for i in range(m-1):
    for j in range(n):
        par[i+1][j]=par[i][par[i][j]]

def hoge(x, y):
    k = 0
    for i in range(m)[::-1]:
        if par[i][x] < y:
            k += 1<<i
            x = par[i][x]
        elif i == 0 and par[i][x] >= y:
            k += 1<<i
    return k

q = int(input())
ans = []
for i in range(q):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    if a > b:
        a,b = b,a
    print(hoge(a,b))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

from bisect import bisect

n = int(input())
x = list(map(int, input().split()))
l = int(input())

m = 20
par = [[-1]*n for i in range(m)]

for i in range(n):
    j = bisect(x, x[i]+l)-1
    par[0][i] = j

for i in range(m-1):
    for j in range(n):
        par[i+1][j]=par[i][par[i][j]]

def hoge(x, y):
    k = 0
    for i in range(m)[::-1]:
        if par[i][x] < y:
            k += 1<<i
            x = par[i][x]
        elif i == 0 and par[i][x] >= y:
            k += 1<<i
    return k

q = int(input())
ans = []
for i in range(q):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    if a > b:
        a,b = b,a
    ans.append(hoge(a, b))

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

from bisect import bisect

n = int(input())
x = list(map(int, input().split()))
l = int(input())

m = 20
par = [[-1]*n for i in range(m)]

for i in range(n-1):
    j = bisect(x, x[i]+l)-1
    par[0][i] = j

for i in range(m-1):
    for j in range(n):
        par[i+1][j]=par[i][par[i][j]]

def hoge(x, y):
    k = 0
    for i in range(m)[::-1]:
        if 0 <= par[i][x] <= y:
            k += 1<<i
            x = par[i][x]
    return k

q = int(input())
ans = []
for i in range(q):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    if a > b:
        a,b = b,a
    ans.append(hoge(a, b))

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from bisect import bisect

n = int(input())
x = list(map(int, input().split()))
l = int(input())

depth = [-1]*n
depth[-1] = 0

m = 20
par = [[-1]*n for i in range(m)]

def dfs(i):
    if depth[i] >= 0:
        return depth[i]
    j = bisect(x, x[i]+l)-1
    if j == n:
        j = n-1
    par[0][i] = j
    depth[i] = dfs(j) + 1
    return depth[i]

for i in range(n):
    dfs(i)

for i in range(m-1):
    for j in range(n):
        par[i+1][j]=par[i][par[i][j]]

def hoge(x, y):
# xからk個上の頂点がy以上になる最小のkを求める
    k = 0
    for i in range(m)[::-1]:
        if 0 <= par[i][x] <= y:
            k += 1<<i
            x = par[i][x]
    return k

q = int(input())
ans = []
for i in range(q):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    if a > b:
        a,b = b,a
    ans.append(hoge(a, b))

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from bisect import bisect_right

n = int(input())
x = list(map(int, input().split()))
l = int(input())

depth = [-1]*n
depth[-1] = 0

m = 20
par = [[-1]*n for i in range(m)]

def dfs(i):
    if depth[i] >= 0:
        return depth[i]
    j = bisect_right(x, x[i]+l)-1
    if j >= n:
        j = n-1
    par[0][i] = j
    depth[i] = dfs(j) + 1
    return depth[i]

for i in range(n):
    dfs(i)

for i in range(m-1):
    for j in range(n):
        par[i+1][j]=par[i][par[i][j]]

def hoge(x, y):
# xからk個上の頂点がy以上になる最小のkを求める
    k = 0
    for i in range(m)[::-1]:
        if 0 <= par[i][x] <= y:
            k += 1<<i
            x = par[i][x]
    return k

q = int(input())
ans = []
for i in range(q):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    if a > b:
        a,b = b,a
    ans.append(hoge(a, b))

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from bisect import bisect_right

n = int(input())
x = list(map(int, input().split()))
l = int(input())

depth = [-1]*n
depth[-1] = 0

m = 18
par = [[-1]*n for i in range(m)]

def dfs(i):
    if depth[i] >= 0:
        return depth[i]
    j = bisect_right(x, x[i]+l)-1
    if j >= n:
        j = n-1
    par[0][i] = j
    depth[i] = dfs(j) + 1
    return depth[i]

for i in range(n):
    dfs(i)

for i in range(m-1):
    for j in range(n):
        par[i+1][j]=par[i][par[i][j]]

def hoge(x, y):
# xからk個上の頂点がy以上になる最小のkを求める
    k = 0
    for i in range(m)[::-1]:
        if 0 <= par[i][x] <= y:
            k += 1<<i
            x = par[i][x]
    return k

q = int(input())
ans = []
for i in range(q):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    if a > b:
        a,b = b,a
    ans.append(hoge(a, b))

print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
N = int(input())
X = list(map(int,input().split()))
L = int(input())
Q = int(input())
qs = [tuple(map(int,input().split())) for i in range(Q)]

if N>1000 or Q>1000:
    exit()

ans = []
for a,b in qs:
    a,b = a-1,b-1
    if a<b:
        l = k = 0
        for i in range(a,b):
            if l + X[i+1]-X[i] > L:
                k += 1
                l = X[i+1]-X[i]
            else:
                l += X[i+1]-X[i]
    else:
        l = k = 0
        for i in range(a,b,-1):
            if l + X[i]-X[i-1] > L:
                k += 1
                l = X[i]-X[i-1]
            else:
                l += X[i]-X[i-1]
    ans.append(k + int(l>0))

print(*ans,sep='\n')

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
import math
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    X = list(map(int, input().split()))
    L = int(input())
    ln = int(math.log(N, 2))
    dpl = [[0] * N for _ in range(ln+1)]
    dpr = [[0] * N for _ in range(ln+1)]
    l = 0
    r = 0
    for i in range(N):
        x = X[i]
        while X[l] + L < x:
            l += 1
        while r < N-1 and x + L >= X[r+1]:
            r += 1
        dpl[0][i] = l
        dpr[0][i] = r
    for k in range(1, ln+1):
        for i in range(N):
            dpl[k][i] = dpl[k-1][dpl[k-1][i]]
            dpr[k][i] = dpr[k-1][dpr[k-1][i]]
    Q = int(input())
    for _ in range(Q):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        ans = 0
        if a < b:
            for k in range(ln+1)[::-1]:
                if dpr[k][a] <= b:
                    a = dpr[k][a]
                    ans += 2**k
            if a < b:
                ans += 1
        else:
            # a > b
            for k in range(ln+1)[::-1]:
                if dpl[k][a] >= b:
                    a = dpl[k][a]
                    ans += 2**k
            if a > b:
                ans += 1
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left, bisect_right
import math
import sys
input = sys.stdin.readline


def main():
    N = int(input())
    X = list(map(int, input().split()))
    L = int(input())
    ln = int(math.log(N, 2))
    dpl = [[0] * N for _ in range(ln+1)]
    dpr = [[0] * N for _ in range(ln+1)]
    l = 0
    r = 0
    for i in range(N):
        x = X[i]
        while X[l] + L < x:
            l += 1
        while r < N-1 and x + L >= X[r+1]:
            r += 1
        dpl[0][i] = l
        dpr[0][i] = r
    for k in range(1, ln+1):
        for i in range(N):
            dpl[k][i] = dpl[k-1][dpl[k-1][i]]
            dpr[k][i] = dpr[k-1][dpr[k-1][i]]
    Q = int(input())
    for _ in range(Q):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        ans = 0
        if a < b:
            for k in range(ln+1)[::-1]:
                if dpr[k][a] <= b:
                    a = dpr[k][a]
                    ans += 2**k
            if a < b:
                ans += 1
        else:
            # a > b
            for k in range(ln+1)[::-1]:
                if dpl[k][a] >= b:
                    a = dpl[k][a]
                    ans += 2**k
            if a > b:
                ans += 1
        print(ans)
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3.6
import bisect
n = int(input())
x = [int(item) for item in input().split()]
l = int(input())
q = int(input())
ab = []
for i in range(q):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    if a > b:
        a, b = b, a
    ab.append((a, b))

dt = [[0] * n for _ in range(18)]
for i, item in enumerate(x):
    dt[0][i] = bisect.bisect_right(x, item + l) - 1

for i in range(1, 18):
    for j in range(n):
        dt[i][j] = dt[i-1][dt[i-1][j]]

for a, b in ab:
    days = 0
    if a == b:
        print(days)
        continue
    for i in range(17, -1, -1):
        if dt[i][a] < b:
            a = dt[i-1][a]
            days += 2**i
    print(days + 1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3.6
import bisect
n = int(input())
x = [int(item) for item in input().split()]
l = int(input())
q = int(input())
ab = []
for i in range(q):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    if a > b:
        a, b = b, a
    ab.append((a, b))

dt = [[0] * n for _ in range(18)]
for i, item in enumerate(x):
    dt[0][i] = bisect.bisect_right(x, item + l) - 1

for i in range(1, 18):
    for j in range(n):
        dt[i][j] = dt[i-1][dt[i-1][j]]

for a, b in ab:
    days = 0
    for i in range(17, -1, -1):
        if dt[i][a] < b:
            a = dt[i-1][a]
            days += 2**i
    print(days + 1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3.6
import bisect
n = int(input())
x = [int(item) for item in input().split()]
l = int(input())
q = int(input())
ab = []
for i in range(q):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    if a > b:
        a, b = b, a
    ab.append((a, b))

dt = [[0] * n for _ in range(18)]
for i, item in enumerate(x):
    dt[0][i] = i
    dt[1][i] = bisect.bisect_right(x, item + l) - 1

for i in range(2, 18):
    for j in range(n):
        dt[i][j] = dt[i-1][dt[i-1][j]]

for a, b in ab:
    days = 0
    for i in range(17, -1, -1):
        if dt[i][a] < b:
            a = dt[i-1][a]
            if i > 0:
                days += 2**(i-1)
            else:
                days += 1
    print(days)

Submission status: Wrong Answer

Solution code:
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(ldp)


def solver(l, r):
    ret = 0
    while l < r:
        d = max(0, np.searchsorted(rdp[:, l], r - l + 1) - 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 = max(0, np.searchsorted(ldp[:, l], r - l + 1) - 1)
        ret += 2 ** d
        l += ldp[d, l]
    return ret


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

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

Submission status: Wrong Answer

Solution code:
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]]


def solver(l, r):
    ret = 0
    while l < r:
        d = max(0, np.searchsorted(rdp[:, l], r - l, side='right') - 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 = max(0, np.searchsorted(ldp[:, l], r - l, side='right') - 1)
        ret += 2 ** d
        l += ldp[d, l]
    return ret


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

Submission status: Wrong Answer

Solution code:
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]]


def solver(l, r):
    ret = 0
    while l < r:
        d = np.searchsorted(rdp[:, l], r - l, side='right') - 1
        ret += 2 ** max(0, 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, side='right') - 1
        ret += 2 ** max(0, d)
        l += ldp[d, l]
    return ret


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

Submission status: Wrong Answer

Solution code:
from math import*
from bisect import*
n,*t=map(int,open(0).read().split())
m=int(log2(n))+1
x=t[:n]
l=t[n]
d=[[bisect(x,y+l)-1for y in x]]+[[0]*n for _ in range(m)]
for i in range(m):
    for j in range(n):
        d[i+1][j]=d[i][d[i][j]]
print(d)
for a,b in zip(t[n+2::2],t[n+3::2]):
    a-=1
    b-=1
    if b<a:a,b=b,a
    c=1
    for i in range(m,-1,-1):
        if d[i][a]<b:
            a=d[i][a]
            c+=2**i
    print(c)

Submission status: Wrong Answer

Solution code:
from math import*
from bisect import*
n,*t=map(int,open(0).read().split())
m=int(log2(n))+1
x=t[:n]
l=t[n]
d=[[bisect(x,y+l)-1for y in x]]+[[0]*n for _ in range(m)]
for i in range(m):
    for j in range(n):
        d[i+1][j]=d[i][d[i][j]]
for a,b in zip(t[n+2::2],t[n+3::2]):
    a-=1
    b-=1
    if b<a:a,b=b,a
    c=0
    for i in range(m,-1,-1):
        if d[i][a]<=b:
            a=d[i][a]
            c+=2**i
    print(c)

Submission status: Wrong Answer

Solution code:
from bisect import*
n,*t=map(int,open(0).read().split())
m=int(n**.5)
x=t[:n]
l=t[n]
d=[[bisect(x,y+l)-1for y in x]]+[[0]*n for _ in range(m)]
for i in range(m):
    for j in range(n):
        d[i+1][j]=d[i][d[i][j]]
for a,b in zip(t[n+2::2],t[n+3::2]):
    a-=1
    b-=1
    if b<a:a,b=b,a
    c=0
    for i in range(m,-1,-1):
        if d[i][a]<=b:
            a=d[i][a]
            c+=2**i
    print(c)

Submission status: Wrong Answer

Solution code:
n,*x=map(int,open(0).read().split())
d=[0]+[10**9]*~-n
l=x[n]
i=t=0
for j,y in enumerate(x[1:n],1):
    t=y-x[i]
    while t>l:
        i+=1
        t=y-x[i]
    d[j]=d[i]+1
for a,b in zip(x[n+2::2],x[n+3::2]):
    print(abs(d[a-1]-d[b-1])or 1)

Submission status: Wrong Answer

Solution code:
n,*x=map(int,open(0).read().split())
d=[0]+[10**9]*~-n
l=x[n]
i=t=0
for j,y in enumerate(x[1:n],1):
    t=y-x[i]
    while t>l:
        i+=1
        t=y-x[i]
    print(i,j,t)
    d[j]=d[i]+1
for a,b in zip(x[n+2::2],x[n+3::2]):
    print(abs(d[a-1]-d[b-1])or 1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

n = int(input())
x = list(map(int, input().split()))
l = int(input())
q = int(input())
query = [list(map(int,input().split())) for i in range(q)]

ruiseki = [0]*n
left = 0
cnt = 0
for i in range(n):
    if left >= n-1:
        break
    right = bisect_right(x, x[left]+l)
    for j in range(left+1, min(right, n)):
        ruiseki[j] = cnt+1
    cnt += 1
    left = right-1

for a, b in query:
    ans = abs(ruiseki[a-1] - ruiseki[b-1])
    if ans == 0:
        ans = 1
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
from functools import partial, reduce
from operator import mul
prod = partial(reduce, mul)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from bisect import bisect

def main():
    N = II()
    X = LI()  # coordinate of hotels
    X.append(INF)  # banpei
    L = II()  # max move distance/day
    Q = II()
    AB = []  # two hotel (a,b)
    for _ in range(Q):
        AB.append(LI_())
    Unreachs = [[] for _ in range(N)]
    # 1day
    for i, x in enumerate(X[:-1]):
        u = bisect(X, x + L)
        Unreachs[i].append(u)
    # day 2, 4, 8, ...
    updated = True
    while updated:
        updated = False
        for i in range(N):
            u = Unreachs[Unreachs[i][-1] - 1][-1]
            updated = updated or (u != Unreachs[i][-1])
            Unreachs[i].append(u)
    # solve
    for a, b in AB:
        if a > b:
            a, b = b, a
        ans = 0
        while True:
            k = bisect(Unreachs[a], b) - 1
            if k < 0:
                ans += 1
                break
            ans += 2 ** k
            a = Unreachs[a][k]
        print(ans)
    return 0

main()