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:
import bisect
import math
N = int(input())
x = list(map(int, input().split()))
L = int(input())

m = int(math.log(max(x), 2) + 1)
#i番目のホテルから2 ** k 日以内に到達可能な
#もっとも右にあるホテル
r = [[-1] * N for k in range(m)]
for i in range(N):
  base = x[i] + L
  p = bisect.bisect_right(x, base)
  #print(p)
  r[0][i] = p - 1

#ダブリング
for k in range(m - 1):
  for i in range(N):
    r[k + 1][i] = r[k][r[k][i]]
#print(r)    
   
def isOK(mid):
  now = a
  pp = int(math.log(mid, 2) + 1)
  for i in range(pp):
    if (mid >> i) & 1:
      now = r[i][now]
      #print(now, a + 1, b + 1, mid)
  if now >= b:
    return True
  else:
    return False
  
Q = int(input())
for i in range(Q):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  if a > b:
    a, b = b, a
  ng = 0
  ok = 2 ** m
  while (abs(ok - ng) > 1):
    mid = int((ok + ng) / 2)
    #print(mid)
    if isOK(mid):
      ok = mid
    else:
      ng = mid
  print(ok)

Submission status: Time Limit Exceeded

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

N = int(input())
x = list(map(int, input().split()))
L = int(input())
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 = 1
    i = a
    d = 0
    while i < b:
        if d + x[i+1] - x[i] <= L:
            d += x[i+1] - x[i]
        else:
            ans += 1
            d = x[i+1] - x[i]
        i += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
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):
    for j in range(pos,n):
      if arr[j]-arr[i]>l:
        dbl[0][i+1]=j
        pos=j
        break
    else:
      dbl[0][i+1]=n
  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: Time Limit Exceeded

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

def check(a,b,n):
  l=n.bit_length()
  for i in range(l):
    if n&(1<<i):
      a=dbl[i][a]
  return a>=b

n=int(input())
arr=list(map(int,input().split()))
l=int(input())
dbl=[[0]*(n+1)]
pos=0
for i in range(n):
  for j in range(pos,n):
    if arr[j]-arr[i]>l:
      dbl[0][i+1]=j
      pos=j
      break
  else:
    dbl[0][i+1]=n
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
    if check(a,b,mid):
      r=mid
    else:
      l=mid
  print(r)

Submission status: Time Limit Exceeded

Solution code:
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 _ in range(17)]
  for i in range(n):
    for j in range(pos,n):
      if arr[j]-arr[i]>l:
        dbl[0][i+1]=j
        pos=j
        break
    else:
      dbl[0][i+1]=n
  for i in range(1,17):
    for j in range(n+1):
      dbl[i][j]=dbl[i-1][dbl[i-1][j]]
  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(17):
        if mid&(1<<i):
          tmp=dbl[i][tmp]
      if tmp>=b:
        r=mid
      else:
        l=mid
    print(r)
calc()

Submission status: Time Limit Exceeded

Solution code:
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):
    for j in range(pos,n):
      if arr[j]-arr[i]>l:
        dbl[0][i+1]=j
        pos=j
        break
    else:
      dbl[0][i+1]=n
  for _ in range(16):
    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(17):
        if mid&(1<<i):
          tmp=dbl[i][tmp]
      if tmp>=b:
        r=mid
      else:
        l=mid
    print(r)
calc()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
arr=list(map(int,input().split()))
l=int(input())
pos=0
dbl=[[0]*(n+1)]
for i in range(n):
  for j in range(pos,n):
    if arr[j]-arr[i]>l:
      dbl[0][i+1]=j
      pos=j
      break
  else:
    dbl[0][i+1]=n
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: Time Limit Exceeded

Solution code:
from bisect import bisect, bisect_left
import sys

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

def search_1(start):
	return bisect(x, x[start] + l) - 1

route = [[] for _ in range(n)]

i = 0 # 親の位置
for i in range(n - 1):
	if route[i] == []:
		j = search_1(i) # カーソルの位置
		num = 1 # 何日目の場所か
		route[i].append(j)
		if route[j] == []:
			route[j] = (i, num)
		else: # 既に他の親が通っている
			route[i] += route[route[j][0]][route[j][1]:]
			continue
		while j < n - 1:
			j = search_1(j)
			num += 1
			route[i].append(j)
			if route[j] == []:
				route[j] = (i, num)
			else: # 既に他の親が通っている
				route[i] += route[route[j][0]][route[j][1]:]
				break
	else:
		continue

# print(route)

def search_2(start, goal):
	if type(route[start]) == type([]):
		return bisect_left(route[start], goal) + 1
	else:
		return bisect_left(route[route[start][0]][route[start][1]:], goal) + 1

q = int(input())
for _ in range(q):
	a, b = map(int, sys.stdin.readline().strip().split())
	if a > b:
		a, b = b, a
	print(search_2(a - 1, b - 1))

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
n = int(input())
x = list(map(int, input().split()))
l = int(input())
q = int(input())

dp_plus = [[0]*(n+1) for i in range(30)]
dp_minus = [[0]*(n+1) for i in range(30)]

for i in range(n):
    now = x[i]
    reach = now + l
    dp_plus[0][i+1] = bisect_right(x, reach)

for i in range(n):
    now = x[i]
    reach = now - l
    dp_minus[0][i+1] = bisect_left(x, reach) + 1



for i in range(29):
    for j in range(1, n+1):
        dp_plus[i+1][j] = dp_plus[i][dp_plus[i][j]]
        dp_minus[i+1][j] = dp_minus[i][dp_minus[i][j]]


for _ in range(q):
    a, b = map(int, input().split())
    ans = 1
    if a < b:
        for i in range(29, -1, -1):
            if dp_plus[i][a] < b:
                a = dp_plus[i][a]
                ans += pow(2, i)

    else:
        for i in range(29, -1, -1):
            if dp_minus[i][a] > b:
                a = dp_minus[i][a]
                ans += pow(2, i)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect


def max_reach(s, d, dest):
    if d == 0:
        return s

    k = 0
    while d >= (1 << k):
        k += 1
    k -= 1

    return max_reach(dest[s][k], d - (1 << k), dest)


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

    a = []
    b = []
    for i in range(Q):
        ta, tb = map(int, input().split())
        a.append(min(ta - 1, tb - 1))
        b.append(max(ta - 1, tb - 1))

    k = 0
    while N >= (1 << k):
        k += 1

    dest = [[0] * (k + 1) for _ in range(N)]
    for i in range(N):
        dest[i][0] = bisect.bisect_right(x, x[i] + L) - 1

    for i in reversed(range(N)):
        for j in range(1, k + 1):
            dest[i][j] = dest[dest[i][j - 1]][j - 1]

    for i in range(Q):
        x1 = a[i]
        x2 = b[i]
        lb = 0
        ub = N
        while (ub - lb) > 1:
            mid = (ub + lb) // 2
            if x2 <= max_reach(x1, mid, dest):
                ub = mid
            else:
                lb = mid
        print(ub)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect


def max_reach(s, d, dest):
    if d == 0:
        return s

    k = 0
    while d >= (1 << k):
        k += 1
    k -= 1

    return max_reach(dest[s][k], d - (1 << k), dest)


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

    a = []
    b = []
    for i in range(Q):
        ta, tb = map(int, input().split())
        a.append(min(ta - 1, tb - 1))
        b.append(max(ta - 1, tb - 1))

    K = 0
    while N >= (1 << K):
        K += 1

    dest = [[0] * (K + 1) for _ in range(N)]
    for i in range(N):
        dest[i][0] = bisect.bisect_right(x, x[i] + L) - 1

    for i in reversed(range(N)):
        for j in range(1, K + 1):
            dest[i][j] = dest[dest[i][j - 1]][j - 1]

    for i in range(Q):
        x1 = a[i]
        x2 = b[i]
        lb = 0
        ub = N
        while (ub - lb) > 1:
            mid = (ub + lb) // 2
            if x2 <= max_reach(x1, mid, dest):
                ub = mid
            else:
                lb = mid
        print(ub)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect


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

    a = []
    b = []
    for i in range(Q):
        ta, tb = map(int, input().split())
        a.append(min(ta - 1, tb - 1))
        b.append(max(ta - 1, tb - 1))

    bin_ma = 1
    ma = 1
    while bin_ma < N:
        bin_ma *= 2
        ma += 1

    dist = [[0] * ma for _ in range(N)]
    for i in range(N):
        dist[i][0] = bisect.bisect_right(x, x[i] + L) - 1

    for i in reversed(range(N)):
        for j in range(1, ma):
            dist[i][j] = dist[dist[i][j - 1]][j - 1]

    def move(x1, x2):
        lb = -1
        ub = ma - 1
        while (ub - lb) > 1:
            mid = (ub + lb) // 2
            idx = dist[x1][mid]
            if idx < x2:
                lb = mid
            else:
                ub = mid

        if dist[x1][ub] == x2:
            return x2, 2 ** ub
        elif ub == 0:
            return x2, 1
        else:
            return ub - 1, 2 ** (ub - 1)

    for q in range(Q):
        x1 = a[q]
        x2 = b[q]
        ans = 0
        while True:
            x1, day = move(x1, x2)
            ans += day
            if x1 == x2:
                print(ans)
                break


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect


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

    a = []
    b = []
    for i in range(Q):
        ta, tb = map(int, input().split())
        a.append(min(ta - 1, tb - 1))
        b.append(max(ta - 1, tb - 1))

    bin_ma = 1
    ma = 1
    while bin_ma < N:
        bin_ma *= 2
        ma += 1

    dist = [[0] * ma for _ in range(N)]
    for i in range(N):
        dist[i][0] = bisect.bisect_right(x, x[i] + L) - 1

    for i in reversed(range(N)):
        for j in range(1, ma):
            dist[i][j] = dist[dist[i][j - 1]][j - 1]

    def move(x1, x2):
        lb = -1
        ub = ma - 1
        while (ub - lb) > 1:
            mid = (ub + lb) // 2
            idx = dist[x1][mid]
            if idx < x2:
                lb = mid
            else:
                ub = mid

        if dist[x1][ub] == x2:
            return x2, 2 ** ub
        else:
            return ub - 1, 2 ** (ub - 1)

    for q in range(Q):
        x1 = a[q]
        x2 = b[q]
        ans = 0
        while True:
            x1, day = move(x1, x2)
            ans += day
            if x1 == x2:
                print(ans)
                break


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
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: Time Limit Exceeded

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


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)

    @lru_cache(maxsize=None)
    def apply(i, n):
        if n == 1:
            return r[i]
        else:
            return apply(apply(i, n//2), n//2)

    @lru_cache(maxsize=None)
    def f(i, n):
        j = i
        for k in range(0, n.bit_length()):
            m = 1 << k
            if n & m:
                j = apply(j, m)
        return j

    ans = []
    for a, b in AB:
        if a > b:
            a, b = b, a
        a -= 1
        b -= 1
        bisect = Bisect(lambda x: f(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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
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()))


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

    ans = []
    for a, b in AB:
        if a > b:
            a, b = b, a
        a -= 1
        b -= 1
        t = 1
        while n[a] < b:
            t += 1
            a = n[a]
        ans.append(t)

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

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 i in range(n-1):
  x = bisect.bisect_right(a,a[i]+d)
  graph[i+1] = x
group = [0]*(n+1)
row = [[] for i in range(n)]
cnt = 0
for i in range(1,n+1):
  if group[i] == 0:
    cnt += 1
    x = i
    while True:
      row[cnt].append(x)
      group[x] = cnt
      if x == n:
        break
      x = graph[x]
q = int(input())
for _ in range(q):
  l,r = map(int,input().split())
  if l>r:
    l,r = r,l
  x = group[l]
  yl = bisect.bisect_left(row[x],l)
  yr = bisect.bisect_left(row[x],r)
  print(yr-yl)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
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 i in range(n-1):
  x = bisect.bisect_right(a,a[i]+d)
  if x == i:
    continue
  graph[i+1] = x
group = [0]*(n+1)
row = [[]]
cnt = 0
stack = []
for i in range(1,n+1):
  if group[i] == 0:
    stack.append(i)
    cnt += 1
    row.append([])
    while stack:
      x = stack.pop()
      row[cnt].append(x)
      group[x] = cnt
      if x != n:
        stack.append(graph[x])
q = int(input())
for _ in range(q):
  l,r = map(int,input().split())
  if l>r:
    l,r = r,l
  x = group[l]
  yl = bisect.bisect_left(row[x],l)
  yr = bisect.bisect_left(row[x],r)
  print(yr-yl)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n = int(input())
a = list(map(int,input().split()))
d = int(input())
graph = [0 for i in range(n+1)]
for i in range(n-1):
  x = bisect.bisect_right(a,a[i]+d)
  if x == i:
    continue
  graph[i+1] = x
group = [0]*(n+1)
row = [[]]
cnt = 0
stack = []
for i in range(1,n+1):
  if group[i] == 0:
    stack.append(i)
    cnt += 1
    row.append([])
    while stack:
      x = stack.pop()
      row[cnt].append(x)
      group[x] = cnt
      if x != n:
        stack.append(graph[x])
q = int(input())
for _ in range(q):
  l,r = map(int,input().split())
  if l>r:
    l,r = r,l
  x = group[l]
  yl = bisect.bisect_left(row[x],l)
  yr = bisect.bisect_left(row[x],r)
  print(yr-yl)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import bisect
n = int(input())
a = list(map(int,input().split()))
d = int(input())
graph = [0 for i in range(n+1)]
for i in range(n-1):
  x = bisect.bisect_right(a,a[i]+d)
  if x == i:
    continue
  graph[i+1] = x
group = [0]*(n+1)
row = [[] for i in range(n+1)]
cnt = 0
stack = []
for i in range(1,n+1):
  if group[i] == 0:
    stack.append(i)
    cnt += 1
    while stack:
      x = stack.pop()
      row[cnt].append(x)
      group[x] = cnt
      if x != n:
        stack.append(graph[x])
q = int(input())
for _ in range(q):
  l,r = map(int,input().split())
  if l>r:
    l,r = r,l
  x = group[l]
  yl = bisect.bisect_left(row[x],l)
  yr = bisect.bisect_left(row[x],r)
  print(yr-yl)

Submission status: Time Limit Exceeded

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

leftX = [-1] * N
rightX = [-1] * N
left = 0

for i, x in enumerate(X):
    while left < N and X[left] < x - L:
        left += 1
    leftX[i] = left

right = N - 1
for i in range(N)[:: -1]:
    x = X[i]
    while right >= 0 and X[right] > x + L:
        right -= 1
    rightX[i] = right

ans = []
for _ in range(Q):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    day = 0
    if fr < to:
        while fr < to:
            day += 1
            fr = rightX[fr]
    else:
        while fr > to:
            day += 1
            fr = leftX[fr]
    ans.append(day)

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

Submission status: Time Limit Exceeded

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]:
                while 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]:
                while dpl[k][a] >= b:
                    a = dpl[k][a]
                    ans += 2**k
            if a > b:
                ans += 1
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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)]
    for i in range(N):
        x = X[i]
        l = bisect_left(X, x - L)
        r = bisect_right(X, x + L) - 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]:
                while 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]:
                while dpl[k][a] >= b:
                    a = dpl[k][a]
                    ans += 2**k
            if a > b:
                ans += 1
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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(40)]
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, 40):
    for j in range(n):
        dt[i][j] = dt[i-1][dt[i-1][j]]

for a, b in ab:
    days = 0
    is_ok = False
    while a < b:
        for i in range(0, 40):
            if dt[i][a] >= b:
                if i == 1:
                    days += 1
                    is_ok = True
                else:
                    a = dt[i-1][a]
                    days += 2**(i-2)
                break
        if is_ok:
            break
    print(days)

Submission status: Time Limit Exceeded

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.T


def solve(l, r):
    ret = 0
    d = len(dp[0]) - 1
    while l + 1 < r:
        while d > 0 and dp[l, d] >= r:
            d -= 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: Time Limit Exceeded

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") - np.arange(N) - 1
for d in range(1, N.bit_length() + 1):
    dp[d] = dp[d - 1] + dp[d - 1][np.arange(N) + dp[d - 1]]

# print(dp)

dp = dp.T


def solve(l, r):
    ret = 0
    d = len(dp[0]) - 1
    while l + 1 < r:
        while d > 0 and dp[l, d] >= r - l:
            d -= 1
        ret += 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: Time Limit Exceeded

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") - np.arange(N) - 1
for d in range(1, N.bit_length() + 1):
    dp[d] = dp[d - 1] + dp[d - 1][np.arange(N) + dp[d - 1]]
dp = dp.T


def solve(l, r):
    ret = 0
    while l + 1 < r:
        d = max(0, np.searchsorted(dp[l], r - l) - 1)
        ret += 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: Time Limit Exceeded

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') - np.arange(N) - 1
for d in range(1, N.bit_length() + 1):
    dp[d] = dp[d - 1] + dp[d - 1][np.arange(N) + dp[d - 1]]


# dp = dp.T

def solve(l, r):
    ret = 0
    tmp = []
    while l + 1 < r:
        d = max(0, np.searchsorted(dp[:, l], r - l) - 1)
        ret += 2 ** d
        l += dp[d, l]
        tmp.append(d)
    if l < r:
        ret += 1
    return ret, tmp


for a, b in AB:
    r, c = solve(min(a, b), max(a, b))
    print(r)