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: Time Limit Exceeded

Solution code:
N = int(input())
X = list(map(int, input().split(' ')))
L = int(input())
Q = int(input())

queries = [tuple(map(lambda s: int(s)-1, input().split(' '))) for _ in range(Q)]


Next = [0]*N
for i in range(N):
  j = i
  bound = X[i] + L
  while j < N and X[j] <= bound:
    j += 1
  Next[i] = j-1

for a,b in queries:
  if a > b:
    a,b = b,a
  cnt = 0
  while a < b:
    a = Next[a]
    cnt += 1
  print(str(cnt))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
x=input().split()
for i in range(n):
    x[i]=int(x[i])
l=int(input())
q=int(input())
ques=[]
for i in range(q):
    currque=input().split()
    a,b=int(currque[0])-1,int(currque[1])-1
    currque[0],currque[1]=min(a,b),max(a,b)
    ques.append(currque)
for que in ques:
    days=1
    time=0
    hotel=que[0]
    while hotel<que[1]:
        hotel+=1
        time+=x[hotel]-x[hotel-1]
        if time>l:
            days+=1
            time=x[hotel]-x[hotel-1]

    print (days)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

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

def calc(i, a, b):
    now = a
    res = 0
    while True:
        # print("dbg", now, X[now])
        # print(bisect_left(X, X[now] + L))
        # print(i, now)
        if now >= b:
            break
        now = bisect_right(X, X[now] + L) - 1
        res += 1
    return res


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

Submission status: Memory Limit Exceeded

Solution code:
# seishin.py
N = int(input())
*X, = map(int, input().split())
L = int(input())

K = 318

D = [[N]*(K+1) for i in range(N)]
j = N-1
for i in range(N-1, -1, -1):
    while j > 0 and X[j] - X[i] > L:
        j -= 1
    D[i][0] = j
for k in range(K):
    for i in range(N):
        if D[i][k] != N:
            D[i][k+1] = D[D[i][k]][k]
def solve(a, b):
    if not a < b:
        a, b = b, a
    res = 1
    for k in range(K, -1, -1):
        if D[a][k] < b:
            a = D[a][k]
            res += 2**k
    return res
Q = int(input())
ans = []
for i in range(Q):
    a, b = map(int, input().split())
    ans.append(solve(a-1, b-1))
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
N = int(input())
X = list(map(int, input().split()))
L = int(input())
from bisect import *
def get_move(X,L,left=False):
  res = [0]*N
  for i in range(N):
    if left:
      res[i] = bisect_left(X,X[i]-L)
    else:
      res[i] = bisect_right(X,X[i]+L)-1
  K = N.bit_length()
  db = [[0]*N for _ in range(K)]
  db[0] = res
  for i in range(1,K):
    for j in range(N):
      db[i][j] = db[i-1][db[i-1][j]]
  return db

def search(dbr,dbl,a,b):
  if a>b:
    db = dbl
    left = True
  else:
    db = dbr
    left = False
  K = N.bit_length()
  ans = 0
  for p in range(K-1,-1,-1):
    if left:
      if b < db[p][a]:
        a = db[p][a]
        ans += 1<<p
    else:
      if b > db[p][a]:
        a = db[p][a]
        ans += 1<<p
  ans += 1
  return ans

dbr = get_move(X,L)
dbl = get_move(X,L,left=True)
Q = int(input())
ans = [0]*Q
for i in range(Q):
  a,b = map(int, input().split())
  ans[i] = search(dbr,dbl,a-1,b-1)
print(*ans, sep='\n')

Submission status: Accepted

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

keta=len(format(n+1,"b"))
nxt = [[0 for _ in range(n)] for _ in range(keta)]
# nxt[k][node] == farthest node-num from node in 2**k days

import bisect
for i in range(n):
    num = x[i]+l
    ind = bisect.bisect_right(x,num)
    nxt[0][i] = ind-1

for k in range(1,keta):
    for i in range(n):
        nxt[k][i]=nxt[k-1][nxt[k-1][i]]

def solve(s,g,day):
    bi=format(day,"b")
    keta=len(bi)-1

    for b in bi:
        if b=="1":
            s=nxt[keta][s]
        keta-=1

    return s>=g
for a,b in ab:
    s=min(a,b)
    g=max(a,b)
    l=0
    r=n
    while r-l>1:
        mid=(l+r)//2
        if solve(s-1,g-1,mid):
            r=mid
        else:
            l=mid

    print(r)

Submission status: Accepted

Solution code:
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N = I()
x = LI()
L = I()

from bisect import bisect_right

arrive = [[0]*N for _ in range(30)]  # arrive[k][i] = i番目(0-indexed)のホテルから2**k日で到達できる最も遠いホテル
for k in range(30):
    if k == 0:
        for i in range(N):
            arrive[0][i] = bisect_right(x,x[i]+L)-1
    else:
        for i in range(N):
            arrive[k][i] = arrive[k-1][arrive[k-1][i]]


def query(a,b):  # (a-1)番目のホテルから(b-1)番目の駅まで移動するのにかかる日数
    a -= 1
    b -= 1
    ans = 1
    for k in range(29,-1,-1):
        if arrive[k][a] >= b:
            continue
        else:
            a = arrive[k][a]
            ans += 1 << k
    print(ans)


Q = I()
for i in range(Q):
    a,b = MI()
    if a > b:
        a,b = b,a
    query(a,b)

Submission status: Accepted

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

N = int(input())
x = list(map(int, input().split()))
L = int(input())
log = 1
while 1 << log < N:
    log += 1
doubling = [[0] * (log + 1) for _ in range(N)]
for i in range(N):
    j = bisect_right(x, x[i] + L) - 1
    doubling[i][0] = j
for l in range(1, log + 1):
    for i in range(N):
        doubling[i][l] = doubling[doubling[i][l-1]][l-1]
Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    ans = 0
    for l in range(log, -1, -1):
        if doubling[a][l] < b:
            ans += 1 << l
            a = doubling[a][l]
    print(ans + 1)

Submission status: Accepted

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

n = int(readline())
x = list(map(int,readline().split()))
l = int(readline())
q = int(readline())
ab = list(map(int,read().split()))

dbl = [[] for _ in range(n)]
j = 0
for i in range(n):
    while(j < n-1):
        if(abs(x[j+1] - x[i]) > l):
            break
        j += 1
    dbl[i].append(j)

for i in range(30):
    if(dbl[0][-1] == n-1):
        break
    for j in range(n):
        dbl[j].append(dbl[ dbl[j][i] ][i])

def calc(a,b):
    if(dbl[a][0] >= b):
        return 1
    ind = bisect.bisect_left(dbl[a],b) - 1
    return 2**ind + calc(dbl[a][ind],b)

ans = []
it = iter(ab)
for a,b in zip(it,it):
    a -= 1
    b -= 1
    a,b = min(a,b),max(a,b)
    ans.append(calc(a,b))

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

Submission status: Accepted

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

n = int(readline())
x = list(map(int,readline().split()))
l = int(readline())
q = int(readline())
ab = list(map(int,read().split()))

dbl_l = [[] for _ in range(n)]
dbl_r = [[] for _ in range(n)]
for dbl,xx in zip([dbl_l,dbl_r],[x,x[::-1]]):
    j = 0
    for i in range(n):
        while(j < n-1):
            if(abs(xx[j+1] - xx[i]) > l):
                break
            j += 1
        dbl[i].append(j)

    for i in range(30):
        if(dbl[0][-1] == n-1):
            break
        for j in range(n):
            dbl[j].append(dbl[ dbl[j][i] ][i])

def calc(a,b,dbl):
    if(dbl[a][0] >= b):
        return 1
    ind = bisect.bisect_left(dbl[a],b) - 1
    return 2**ind + calc(dbl[a][ind],b,dbl)

ans = []
it = iter(ab)
for a,b in zip(it,it):
    a -= 1
    b -= 1
    if(a<b):
        ans.append(calc(a,b,dbl_l))
    else:
        a,b = n-1-a,n-1-b
        ans.append(calc(a,b,dbl_r))

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

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
x = list(map(int, input().split()))
l = int(input())
q = int(input())
ps = [None]*n
# ps2 = [None]*n
j = 0
for i in range(n):
    if j<i:
        j = i
    while j+1<n and x[j+1]-x[i]<=l:
        j += 1
    ps[i] = j
# ダブリング
def double(ps):
    # global: n=psのサイズ
    k = 0
    n = len(ps)
    while pow(2,k)<n:
        k += 1
    prev = [[None]*n for _ in range(k)] # ノードjから2^i個上の上司
    for j in range(n):
        prev[0][j] = ps[j]
    for i in range(1,k):
        for j in range(n):
            p = prev[i-1][j]
            if p>=0:
                prev[i][j] = prev[i-1][p]
            else:
                prev[i][j] = p
    return prev
dl = double(ps)
ans = [None]*q
def sub(a,b,x):
    for k in range(len(dl)-1, -1, -1):
        if x>=pow(2,k):
            x-=pow(2,k)
            a = dl[k][a]
    return a>=b
        
        
for i in range(q):
    a,b = map(lambda x: int(x)-1, input().split())
    a,b = min(a,b), max(a,b)
#     print(a,b)
    res = 0
    tmp = float("inf")
    l = 0
    r = n
    while l+1<r:
        m = (l+r)//2
        if sub(a,b,m):
            r = m
        else:
            l = m
    ans[i] = r
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
x = list(map(int, input().split()))
l = int(input())
q = int(input())
ps = [None]*n
# ps2 = [None]*n
j = 0
for i in range(n):
    if j<i:
        j = i
    while j+1<n and x[j+1]-x[i]<=l:
        j += 1
    ps[i] = j
# ダブリング
def double(ps):
    # global: n=psのサイズ
    k = 0
    n = len(ps)
    while pow(2,k)<n:
        k += 1
    prev = [[None]*n for _ in range(k)] # ノードjから2^i個上の上司
    for j in range(n):
        prev[0][j] = ps[j]
    for i in range(1,k):
        for j in range(n):
            p = prev[i-1][j]
            if p>=0:
                prev[i][j] = prev[i-1][p]
            else:
                prev[i][j] = p
    return prev
dl = double(ps)
ans = [None]*q
for i in range(q):
    a,b = map(lambda x: int(x)-1, input().split())
    a,b = min(a,b), max(a,b)
#     print(a,b)
    res = 0
    tmp = float("inf")
    for k in range(len(dl)-1, -1, -1):
        if dl[k][a]<b:
            a = dl[k][a]
            res += pow(2,k)
#         elif dl[k][a]==b:
#             tmp = res+pow(2,k)
#             break
        else:
            tmp = min(tmp, res+pow(2,k))
    ans[i] = tmp
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n = I()
x = LI() + [INF]
l = I()
q = I()
db = [[0] * n for _ in range(31)]
now = 0
for i in range(n):
    while x[i] + l >= x[now + 1]:
        now += 1
    db[0][i] = now

for j in range(1, 31):
    for k in range(n):
        db[j][k] = db[j - 1][db[j - 1][k]]

for _ in range(q):
    a, b = LI()
    if a > b:
        a, b = b, a
    a -= 1
    b -= 1
    ret = 0
    for kk in range(30, -1, -1):
        if db[kk][a] < b:
            a = db[kk][a]
            ret += 2 ** kk
    print(ret + 1)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
read = sys.stdin.read
readline = sys.stdin.readline

n, = map(int,readline().split())
*x, = map(int,readline().split())
l,q,*ab = map(int,read().split())


from bisect import bisect_left, bisect_right

M = 19
"""
L = [[bisect_left(x,i-l) for i in x]]
for i in range(M):
    LL = [L[-1][L[-1][i]] for i in range(n)]
    L.append(LL)

"""
R = [[bisect_right(x,i+l)-1 for i in x]]
for i in range(M):
    RR = [R[-1][R[-1][i]] for i in range(n)]
    R.append(RR)

#for i in R: print(i)

mp = iter(ab)
for a,b in zip(mp,mp):
    a -= 1
    b -= 1
    if a > b: a,b = b,a
    
    ans = 0
    for i in range(M,-1,-1):
        if R[i][a] < b:
            ans += 1<<i
            a = R[i][a]
    print(ans+1)

Submission status: Accepted

Solution code:
import bisect

n=int(input())
arr=list(map(int,input().split()))
l=int(input())
pos=0
dbl=[[0]*(n+1)]
for i in range(n):
  dbl[0][i+1]=bisect.bisect_right(arr,arr[i]+l)
for _ in range(20):
  tmp=[0]*(n+1)
  for i in range(n+1):
    tmp[i]=dbl[-1][dbl[-1][i]]
  dbl.append(tmp)
q=int(input())
for _ in range(q):
  a,b=map(int,input().split())
  if a>b:
    a,b=b,a
  l=0
  r=b-a+1
  while r-l!=1:
    mid=(l+r)//2
    tmp=a
    for i in range(20):
      if mid&(1<<i):
        tmp=dbl[i][tmp]
    if tmp>=b:
      r=mid
    else:
      l=mid
  print(r)

Submission status: Accepted

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

def calc():
  n=int(input())
  arr=list(map(int,input().split()))
  l=int(input())
  pos=0
  dbl=[[0]*(n+1)]
  for i in range(n):
      dbl[0][i+1]=bisect.bisect_right(arr,arr[i]+l)
  for _ in range(n.bit_length()-1):
    tmp=[0]*(n+1)
    for i in range(n+1):
      tmp[i]=dbl[-1][dbl[-1][i]]
    dbl.append(tmp)
  q=int(input())
  for _ in range(q):
    a,b=map(int,input().split())
    if a>b:
      a,b=b,a
    l=0
    r=b-a+1
    while r-l!=1:
      mid=(l+r)//2
      tmp=a
      for i in range(mid.bit_length()):
        if mid&(1<<i):
          tmp=dbl[i][tmp]
      if tmp>=b:
        r=mid
      else:
        l=mid
    print(r)
calc()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    x = LI()
    L = NI()
    m = N.bit_length()
    f = [[N-1] * N for _ in range(m)]
    j = 0
    for i in range(N-1):
        while x[i] + L >= x[j+1]:
            j += 1
            if j >= N-1: break
        else:
            f[0][i] = j
            continue
        break
    for k in range(1,m):
        for i in range(N):
            f[k][i] = f[k-1][f[k-1][i]]

    for _ in range(NI()):
        ans = 0
        a,b = _LI()
        if a > b: a,b = b,a

        for k in range(m-1,-1,-1):
            if f[k][a] < b:
                a = f[k][a]
                ans += 2**k
        print(ans+1)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    x = LI() + [INF]
    L = NI()
    m = N.bit_length()
    f = [[N-1] * N for _ in range(m)]
    j = 1
    for i in range(N-1):
        while x[i] + L >= x[j+1]:
            j += 1
            if j >= N-1: break
        f[0][i] = j
    for k in range(1,m):
        for i in range(N):
            f[k][i] = f[k-1][f[k-1][i]]

    for _ in range(NI()):
        ans = 0
        a,b = _LI()
        if a > b: a,b = b,a

        for k in range(m-1,-1,-1):
            if f[k][a] < b:
                a = f[k][a]
                ans += 2**k
        print(ans+1)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
X = LI()
l = I()
log_n = (n - 1).bit_length()
doubling = [[n] * n for _ in range(log_n)]
for i in range(n - 1):
    doubling[0][i] = bisect_right(X, X[i] + l) - 1

for j in range(1, log_n):
    for k in range(n):
        if doubling[j - 1][k] == n:
            continue
        doubling[j][k] = doubling[j - 1][doubling[j - 1][k]]
q = I()
for _ in range(q):
    a, b = LI()
    if a > b:
        a, b = b, a
    a -= 1
    b -= 1
    ans = 0
    for m in range(log_n - 1, -1, -1):
        if doubling[m][a] < b:
            a = doubling[m][a]
            ans += 2 ** m
    print(ans + 1)

Submission status: Accepted

Solution code:
import sys,bisect

input=sys.stdin.readline

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

doubling=[[-1 for i in range(N)] for j in range(20)]

for i in range(N):
    npos=x[i]+L
    index=bisect.bisect_right(x,npos)
    doubling[0][i]=index-1

for i in range(1,20):
    for j in range(N):
        doubling[i][j]=doubling[i-1][doubling[i-1][j]]

forward=[[-1 for i in range(N)] for j in range(20)]

for i in range(N):
    forward[0][i]=i

for i in range(1,20):
    for j in range(N):
        forward[i][j]=doubling[i-1][forward[i-1][j]]

for _ in range(int(input())):
    a,b=map(int,input().split())
    a-=1;b-=1
    if a>b:
        a,b=b,a
    res=0
    for i in range(19,-1,-1):
        if b>forward[i][a]:
            a=doubling[i][a]
            res+=2**i
    print(res)

Submission status: Accepted

Solution code:
import sys,bisect

input=sys.stdin.readline

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

doubling=[[-1 for i in range(N)] for j in range(20)]
backdoubling=[[-1 for i in range(N)] for j in range(20)]

for i in range(N):
    npos=x[i]+L
    index=bisect.bisect_right(x,npos)
    doubling[0][i]=index-1

for i in range(1,20):
    for j in range(N):
        doubling[i][j]=doubling[i-1][doubling[i-1][j]]

for i in range(N):
    npos=x[i]-L
    index=bisect.bisect_left(x,npos)
    backdoubling[0][i]=index

for i in range(1,20):
    for j in range(N):
        backdoubling[i][j]=backdoubling[i-1][backdoubling[i-1][j]]

def forward(num,start):
    for i in range(20):
        if num>>i &1==1:
            start=doubling[i][start]
    return start

def back(num,start):
    for i in range(20):
        if num>>i &1==1:
            start=backdoubling[i][start]
    return start


for _ in range(int(input())):
    a,b=map(int,input().split())
    a-=1;b-=1
    if b>=a:
        s=0
        e=N
        while e-s>1:
            test=(e+s)//2
            if forward(test,a)>=b:
                e=test
            else:
                s=test
        if forward(s,a)>=b:
            print(s)
        else:
            print(e)
    else:
        s=0
        e=N
        while e-s>1:
            test=(e+s)//2
            if b>=back(test,a):
                e=test
            else:
                s=test
        if b>=back(s,a):
            print(s)
        else:
            print(e)

Submission status: Accepted

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

def main():
  n = int(input())
  X = list(map(int, input().split()))
  l = int(input())
  U = 17
  dp = [[0]*n for _ in range(U+1)]
  for i, x in enumerate(X):
    t = bisect.bisect_left(X, x+l)
    dp[0][i] = bisect.bisect_right(X, x+l) - 1
  for k in range(U):
    for i in range(n):
      dp[k+1][i] = dp[k][dp[k][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
    res = 1
    for k in range(U, -1, -1):
      if dp[k][a] < b:
        a = dp[k][a]
        res += (1<<k)
    print(res)
if __name__ == "__main__":
  main()

Submission status: Accepted

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

n = int(input())
X = list(map(int, input().split()))
l = int(input())
U = 17
dp = [[0]*n for _ in range(U+1)]
for i, x in enumerate(X):
  t = bisect.bisect_left(X, x+l)
  dp[0][i] = bisect.bisect_right(X, x+l) - 1
for k in range(U):
  for i in range(n):
    dp[k+1][i] = dp[k][dp[k][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
  res = 1
  for k in range(U, -1, -1):
    if dp[k][a] < b:
      a = dp[k][a]
      res += (1<<k)
    if a == b:
      break
  print(res)

Submission status: Accepted

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

n = int(input())
X = list(map(int, input().split()))
l = int(input())
U = 17
dp = [[0]*n for _ in range(U+1)]
for i, x in enumerate(X):
  t = bisect.bisect_left(X, x+l)
  dp[0][i] = bisect.bisect_right(X, x+l) - 1
for k in range(U):
  for i in range(n):
    dp[k+1][i] = dp[k][dp[k][i]]
def test(x, a, b):
  for i in range(U, -1, -1):
    if x >> i & 1:
      a = dp[i][a]
  return a >= b
def solve(a, b):
  if a > b:
    a, b = b, a
  ng = 0
  ok = n-1
  while ok - ng > 1:
    mid = (ng + ok) // 2
    if test(mid, a, b):
      ok = mid
    else:
      ng = mid
  print(ok)
q = int(input())
for _ in range(q):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  solve(a, b)

Submission status: Accepted

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    N = int(input())
    x = list(map(int, input().split()))
    L = int(input())
    Q = int(input())

    LOG = 30    # 30 > log2(10**9)
    nxt = [[-1]*N for _ in range(LOG)]
    for i in range(N):
        nxt[0][i] = bisect.bisect_left(x, x[i]+L+1) - 1

    for k in range(LOG-1):
        for i in range(N):
            if nxt[k][i] == -1:
                nxt[k+1][i] = -1
            else:
                nxt[k+1][i] = nxt[k][nxt[k][i]]

    for _ in range(Q):
        a, b = map(int, input().split())
        if a > b:
            a, b = b, a
        a -= 1
        b -= 1
        ans = 0
        for k in reversed(range(LOG)):
            if nxt[k][a] < b:
                a = nxt[k][a]
                ans += 2 ** k
        print(ans + 1)



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from functools import lru_cache
import sys
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


class Bisect:
    def __init__(self, func):
        self.__func = func

    def bisect_left(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if self.__func(mid) < x:
                lo = mid+1
            else:
                hi = mid
        return lo

    def bisect_right(self, x, lo, hi):
        while lo < hi:
            mid = (lo+hi)//2
            if x < self.__func(mid):
                hi = mid
            else:
                lo = mid+1
        return lo


class Doubling():
    def __init__(self, N, a0):
        self.N = N
        self.nt = [[None] * N for i in range(N.bit_length())]
        for i, a in enumerate(a0):
            self.nt[0][i] = a

        for i in range(1, len(self.nt)):
            for j in range(N):
                if self.nt[i-1][j] is None:
                    self.nt[i][j] = None
                else:
                    self.nt[i][j] = self.nt[i-1][self.nt[i-1][j]]

    def apply(self, i, n):
        j = i
        for k in range(n.bit_length()):
            m = 1 << k
            if m & n:
                j = self.nt[k][j]
            if j is None:
                break
        return j



def slv(N, X, L, Q, AB):
    r = [0]
    for x in X:
        t = -1
        for j in range(r[-1], len(X)):
            if X[j] - x <= L:
                t = j
            else:
                break
        r.append(t)
    r.pop(0)

    d = Doubling(N, r)

    ans = []
    for a, b in AB:
        if a > b:
            a, b = b, a
        a -= 1
        b -= 1
        bisect = Bisect(lambda x: d.apply(a, x))
        i = bisect.bisect_left(b, 0, len(X)+1)
        ans.append(i)

    return ans


def main():
    N = read_int()
    X = read_int_n()
    L = read_int()
    Q = read_int()
    AB = [read_int_n() for _ in range(Q)]
    print(*slv(N, X, L, Q, AB), sep='\n')


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    x = list(map(int, input().split()))
    l = int(input())
    q = int(input())
    ab = [list(map(lambda x:int(x)-1, input().split())) for _ in [0]*q]
    doubling = [[] for _ in [0]*n]
    j = 0
    for i in range(n):
        while j < n:
            if x[j]-x[i] > l:
                doubling[i].append(j-1)
                break
            else:
                j += 1
    for i in range(n-1, -1, -1):
        if not doubling[i]:
            doubling[i].append(n-1)
        else:
            break
    for _ in range(16):
        for i in range(n):
            doubling[i].append(doubling[doubling[i][-1]][-1])
    for a, b in ab:
        if a > b:
            a, b = b, a
        ans = 0
        j = 16
        while j >= 0:
            if doubling[a][j] >= b:
                j -= 1
            else:
                a = doubling[a][j]
                ans += 2**j
        if a == b:
            print(ans)
        else:
            print(ans+1)


main()

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    x = list(map(int, input().split()))
    l = int(input())
    q = int(input())
    ab = [list(map(lambda x:int(x)-1, input().split())) for _ in [0]*q]
    doubling = [[] for _ in [0]*n]
    j = 0
    for i in range(n):
        while j < n:
            if x[j]-x[i] > l:
                doubling[i].append(j-1)
                break
            else:
                j += 1
    for i in range(n-1, -1, -1):
        if not doubling[i]:
            doubling[i].append(n-1)
        else:
            break
    for _ in range(16):
        for i in range(n):
            doubling[i].append(doubling[doubling[i][-1]][-1])
    for a, b in ab:
        if a > b:
            a, b = b, a
        ans = 0
        j = 16
        while j >= 0:
            if doubling[a][j] >= b:
                j -= 1
            else:
                a = doubling[a][j]
                ans += 2**j
        if a == b:
            print(ans)
        else:
            print(ans+1)


main()

Submission status: Accepted

Solution code:
import bisect


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

log_size = n.bit_length() + 1
double = [[0] * n for i in range(log_size)]

for i in range(n):
    double[0][i] = bisect.bisect_right(x, x[i] + l) - 1

for k in range(1, log_size):
    for i in range(n):
        double[k][i] = double[k - 1][double[k - 1][i]]
        
for a, b in query:
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    ans = 10 ** 18
    tmp = 0
    for k in range(log_size)[::-1]:
        if double[k][a] >= b:
            ans = min(ans, 2 ** k + tmp)
        else:
            a = double[k][a]
            tmp += 2 ** k
    print(ans)

Submission status: Accepted

Solution code:
import math
from bisect import bisect_left, bisect_right

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

LOGN = int(math.log(N) / math.log(2)) + 1
parent = [[-1] * N for _ in range(LOGN + 1)]

# Update for k
for k in range(LOGN + 1):
    for i in range(N):
        if k == 0:
            parent[k][i] = bisect_right(X, X[i] + L) - 1
        else:
            parent[k][i] = parent[k - 1][parent[k - 1][i]]

def find(a, b):
    num = 0
    u = a
    while True:
        k = 0
        for i in range(LOGN + 1):
            if parent[i][u] >= b:
                k = i
                break
                
        if k == 0:
            num += 1
            break
        num += pow(2, k - 1)
        u = parent[k - 1][u]
        
    return num

for a, b in Y:
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    print(find(a, b))