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: Accepted

Solution code:
import sys
input = sys.stdin.readline
from bisect import *

def judge(a, b, x):
    now = a
    c = 0
    
    while x>0:
        if x&1:
            now = dp[c][now]
        
        x >>= 1
        c += 1
    
    return now>=b
    
def binary_search(a, b):
    l, r = 0, N-1
    
    while l<=r:
        m = (l+r)//2
        
        if judge(a, b, m):
            r = m-1
        else:
            l = m+1
    
    return l

N = int(input())
x = list(map(int, input().split()))
L = int(input())
log_size = 22
dp = [[0]*N for _ in range(log_size)]

for i in range(N):
    dp[0][i] = bisect_right(x, x[i]+L)-1
    
for i in range(1, log_size):
    for j in range(N):
        dp[i][j] = dp[i-1][dp[i-1][j]]

Q = int(input())

for _ in range(Q):
    a, b = map(int, input().split())
    a, b = min(a, b)-1, max(a, b)-1
    print(binary_search(a, b))

Submission status: Accepted

Solution code:
import bisect
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int,input().split()))
d = int(input())
graph = [[0 for i in range(n+1)] for j in range(18)]
for i in range(n):
  x = bisect.bisect_right(a,a[i]+d)
  graph[0][i+1] = x
for j in range(1,18):
  for i in range(n):
    t = graph[j-1][i+1]
    graph[j][i+1] = graph[j-1][t]
q = int(input())
for _ in range(q):
  x,y = map(int,input().split())
  x,y = min(x,y),max(x,y)
  ans = 0
  for j in range(18)[::-1]:
    if graph[j][x] < y:
      ans += 2**j
      x = graph[j][x]
    if j == 0 and x < y:
      ans += 1
  print(ans)

Submission status: Accepted

Solution code:
#!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.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()
    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
        for i in range(h)[::-1]:
            if f[a][i] < b:
                a = f[a][i]
                ans += 1<<i
        print(ans+1)
    return

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

Submission status: Accepted

Solution code:
#!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
        for i in range(h)[::-1]:
            if f[a][i] < b:
                a = f[a][i]
                ans += 1<<i
        print(ans+1)
    return

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
L = int(input())
k = 1
while a[-1] // (L * pow(2, k)): k += 1
e = [[0] * k for _ in range(N)]
for i in range(N):
  t = L + a[i]
  ok = i
  ng = N
  while ng - ok > 1:
    m = (ok + ng) // 2
    if a[m] <= t: ok = m
    else: ng = m
  e[i][0] = ok
for j in range(len(e[i]) - 1):
  for i in range(N):
    x = e[i][j]
    e[i][j + 1] = e[x][j]
#print(e)

def doubling(u, v):
  if u == v: return 0
  ok = -1
  ng = len(e[u])
  while ng - ok > 1:
    m = (ok + ng) // 2
    if e[u][m] < v: ok = m
    else: ng = m
  if ok < 0: return 1
  return doubling(e[u][ok], v) + pow(2, ok)

Q = int(input())
for _ in range(Q):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  if x > y: x, y = y, x
  print(doubling(x, y))

Submission status: Accepted

Solution code:
import sys
from bisect import bisect

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

reachable = [[bisect(xxx, x + l) - 1 for x in xxx]]
while reachable[-1][0] < n - 1:
    rp = reachable[-1]
    reachable.append(list(map(rp.__getitem__, rp)))

q = int(input())
buf = []
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    ans = 0
    for i in range(len(reachable) - 1, -1, -1):
        ria = reachable[i][a]
        if ria >= b:
            continue
        ans += 1 << i
        a = ria
    if a != b:
        ans += 1
    buf.append(ans)

print('\n'.join(map(str, buf)))

Submission status: Accepted

Solution code:
# verified: ABC014-D
# calculate LCA O(logN) for each query

# prev[i][k]: 2^k parent of node i 
# Depth[i]: Depth of node i from 0

class LCA():
    def __init__(self, graph, rootNode=0):
        self.graph = graph
        self.N = len(graph)
        self.Log_N = (self.N-1).bit_length()
        self.rootNode = rootNode
        # BFS
        self.prev = [None]*self.N
   
        self.Depth = [-1]*self.N
        q = [self.rootNode]
        self.Depth[self.rootNode] = 0
        d = 0
        while q:
            qq = []
            d += 1
            for p in q:
                for np in self.graph[p]:
                    if self.Depth[np] == -1:
                        self.prev[np] = p
                        self.Depth[np] = d
                        qq.append(np)
            q = qq

        # construct
        self.kprev = [self.prev]
        S = self.prev
        for k in range(self.Log_N):
            T = [None]*self.N
            for i in range(self.N):
                if S[i] is None:
                    continue
                T[i] = S[S[i]]
            self.kprev.append(T)
            S = T

    # LCA
    def query(self, u, v):
        dd = self.Depth[v] - self.Depth[u]
        if dd < 0:
            u, v = v, u
            dd = -dd
        
        # set same Depth
        for k in range(self.Log_N+1):
            if dd & 1:
                v = self.kprev[k][v]
            dd >>= 1
        
        if u == v:
            return u
        
        for k in reversed(range(self.Log_N)):
            pu = self.kprev[k][u]
            pv = self.kprev[k][v]
            if pu != pv:
                u, v = pu, pv
        
        return self.kprev[0][u]

"""
if __name__ == "__main__":
    import sys
    input = sys.stdin.readline

    N = int(input())
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    
    Q = int(input())
    Query = [list(map(int, input().split())) for _ in range(Q)]

    lca = LCA(graph)
    for a, b in Query:
        r = lca.query(a-1, b-1)
        d = lca.Depth[a-1] + lca.Depth[b-1] - 2*lca.Depth[r]
        print(d+1)
"""

import sys
input = sys.stdin.readline
from bisect import bisect_right

N = int(input())
A = list(map(int, input().split()))
L = int(input())
Q = int(input())
Query = [list(map(int, input().split())) for _ in range(Q)]

graph = [[] for _ in range(N)]
for i, a in enumerate(A):
    j = bisect_right(A, a+L)-1
    graph[j].append(i)
    graph[i].append(j)


lca = LCA(graph, rootNode=N-1)
for a, b in Query:
    d = 0
    a -= 1; b-= 1
    if b < a:
        a, b = b, a
    for k in reversed(range(lca.Log_N)):
        nextnode = lca.kprev[k][a]
        if nextnode is None:
            continue
        else:
            if nextnode == b:
                d += 1<<k
                break
            elif A[nextnode] < A[b]:
                d += 1<<k
                a = nextnode
    if nextnode != b:
        d += 1
    print(d)

Submission status: Accepted

Solution code:
import bisect

def wantp(p,day):

    for i in range(len(db)):
        i = len(db)-1-i

        if day & (2 ** i) > 0:
            p = db[i][p]

        #print (day,i)

    return p


N = int(input())
x = list(map(int,input().split()))
L = int(input())

able = []

for i in range(N):

    able.append(bisect.bisect_right(x,x[i] + L) - 1)


db = [able]

while min(db[-1]) != N-1:

    new = []

    for i in range(N):

        new.append(db[-1][db[-1][i]])

    db.append(new)


Q = int(input())

for loop in range(Q):

    a,b = map(int,input().split())
    if a > b:
        t = a
        a = b
        b = t
    a -= 1
    b -= 1

    l = 0
    r = 2 ** len(db)

    while r-l != 1:

        m = (l+r) // 2

        np = wantp(a,m)
        #print (a,m,np)

        if np < b:
            l = m
        else:
            r = m

    print (r)

Submission status: Accepted

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+1)

Submission status: Accepted

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 = 1
        for j in range(N)[::-1]:
            if p[a][j] < b:
                a = p[a][j]
                ans += 1<<j
        print(ans)
    return

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

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline
import bisect

INF = float("inf")

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N = int(input())
	X = getlist()
	X.append(INF)
	L = int(input())
	double = [[0] * (N + 1) for i in range(20)]
	for i in range(N):
		p = bisect.bisect_left(X, X[i] + L + 1)
		double[0][i] = p - 1
	for i in range(20):
		double[i][N] = INF
	
	for i in range(1, 20):
		for j in range(N):
			double[i][j]  = double[i - 1][double[i - 1][j]]

	# for i in range(5):
	# 	print(double[i])

	Q = int(input())
	for i in range(Q):
		a, b = sorted(getlist())
		a -= 1; b -= 1
		ans = 0
		for j in range(20):
			if double[19 - j][a] < b:
				a = double[19 - j][a]
				ans += 1 << (19 - j)

		print(ans + 1)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

N = int(readline())
X = np.array(readline().split(),np.int64)
L = int(readline())
Q = int(readline())
AB = np.array(read().split(),np.int64).reshape(-1,2)

AB -= 1
AB.sort(axis = 1)
A = AB[:,0]; B = AB[:,1]

# 2^n 日あれば、どこまでいけるのか

U = 20
dp = [np.full(N,N-1,np.int64) for _ in range(U)]

dp[0] = np.searchsorted(X, X + L, side = 'right') - 1

for n in range(1,U):
    dp[n] = dp[n-1][dp[n-1]]

days = np.ones(Q,np.int64)
for n in reversed(range(U)):
    x = dp[n][A]
    bl = x < B
    days[bl] += (1 << n)
    A[bl] = x[bl]
print('\n'.join(map(str,days)))

Submission status: Accepted

Solution code:
def examE():
    N = I()
    X = LI()
    L = I(); Q = I()
    n = N.bit_length()+1
    dp = [[0] * n for _ in range(N)]
    for i in range(N):
        dp[i][0] = bisect.bisect_right(X, X[i] + L) - 1
    for i in range(1, n):
        for j in range(N):
            if dp[j][i - 1] < N:
                index = dp[dp[j][i - 1]][i - 1]
                if index == j:
                    dp[j][i] = N
                else:
                    dp[j][i] = index
            else:
                dp[j][i] = N
    def fast_day(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.bisect_left(dp[a], b) - 1)
            #最低かかる2**?の日数
            a = dp[a][c]
            #そこまで行く
            res += 2 ** c
    for _ in range(Q):
        a, b = map(int, input().split())
        print(fast_day(a - 1, b - 1))
#    print(dp)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examE()

Submission status: Accepted

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)

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: Accepted

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()+1
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: Accepted

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+1

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: Accepted

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]
    return k+1

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: Accepted

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
        else:
            # a > b
            for k in range(ln+1)[::-1]:
                if dpl[k][a] > b:
                    a = dpl[k][a]
                    ans += 2**k
        print(ans+1)


if __name__ == "__main__":
    main()

Submission status: Accepted

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: Accepted

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][a]
            days += 2**i
    print(days + 1)

Submission status: Accepted

Solution code:
import bisect
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, N.bit_length() + 1), dtype=int)
dp[:, 0] = np.searchsorted(X, X + L, side="right") - 1
for d in range(1, N.bit_length() + 1):
    dp[:, d] = dp[dp[:, d - 1], d - 1]
dp = dp.tolist()


def solve(l, r):
    ret = 0
    while l + 1 < r:
        d = max(0, bisect.bisect_left(dp[l], r) - 1)
        ret += pow(2, d)
        l = dp[l][d]
    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')

Submission status: Accepted

Solution code:
import bisect
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.T.tolist()


def solve(l, r):
    ret = 0
    while l + 1 < r:
        d = max(0, bisect.bisect_left(dp[l], r) - 1)
        ret += pow(2, d)
        l = dp[l][d]
    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')

Submission status: Accepted

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)]

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')

Submission status: Accepted

Solution code:
import bisect

N = int(input())
x = list(map(int, input().split()))
L = int(input())

dest = []
dest_1 = [0] * N
for i in range(N):
    dest_1[i] = bisect.bisect_left(x, x[i] + L + 0.5) - 1
dest.append(dest_1)
for i in range(1, len(bin(N - 1)) - 1):
    dest_prev = dest[i - 1]
    dest_i = [0] * N
    for j in range(N):
        dest_i[j] = dest_prev[dest_prev[j]]
    dest.append(dest_i)

Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    k = len(dest) - 1
    ans = 0
    while True:
        d = dest[k][a]
        if d >= b:
            if k > 0:
                k -= 1
            else:
                ans += 1
                break
        else:
            ans += 2 ** k
            a = d
    print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from bisect import bisect_right
n=int(input())
X=tuple(map(int,input().split()))
l=int(input())
q=int(input())
D=[[0]*n for _ in range(18)]
for i in range(n):
    D[0][i]=bisect_right(X,X[i]+l)-1
for k in range(1,18):
    for i in range(n):
        D[k][i]=D[k-1][D[k-1][i]]

def query(a,b):
    ret=0
    while True:
        for k in range(18):
            if D[k][a]>=b:
                break
        if k==0:
            ret+=1
            return ret
        k-=1
        ret+=pow(2,k)
        a=D[k][a]

for _ in range(q):
    a,b=map(int,input().split())
    if a>b:
        a,b=b,a
    a-=1; b-=1
    print(query(a,b))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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=1
    for i in range(m,-1,-1):
        if d[i][a]<b:
            a=d[i][a]
            c+=2**i
    print(c)