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


def solve(l, r):
    ret = 0
    d = IINF
    while l < r:
        d = np.searchsorted(dp[:d + 1, l], r - l)
        if dp[d, l] == r - l:
            ret += pow(2, d)
            break
        if d > 0:
            d -= 1
        ret += pow(2, d)
        l += dp[d, l]
    return ret


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

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


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


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

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


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


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

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] - 1] + X + [X[-1] + 1]
X = np.array(X, dtype=int)
# rdp[d][i]: i番のホテルから(2^d)日で何個右までいけるか
rdp = np.zeros((N.bit_length() + 1, N), dtype=int)
rdp[0] = np.searchsorted(X, X + L, side='right') - np.arange(N) - 1
for d in range(1, N.bit_length() + 1):
    rdp[d] = rdp[d - 1] + rdp[d - 1][np.arange(N) + rdp[d - 1]]

X = -X[::-1]
# ldp[d][i]: i番のホテルから(2^d)日で何個左までいけるか
ldp = np.zeros((N.bit_length() + 1, N), dtype=int)
ldp[0] = np.searchsorted(X, X + L, side='right') - np.arange(N) - 1
for d in range(1, N.bit_length() + 1):
    ldp[d] = ldp[d - 1] + ldp[d - 1][np.arange(N) + ldp[d - 1]]


# print(rdp)
# print(ldp)


def solver(l, r):
    ret = 0
    while l < r:
        d = np.searchsorted(rdp[:, l], r - l)
        if rdp[d, l] == r - l:
            ret += 2 ** d
            break
        if d > 0:
            d -= 1
        ret += 2 ** d
        l += rdp[d, l]
    return ret


def solvel(l, r):
    r = N - r - 1
    l = N - l - 1
    ret = 0
    while l < r:
        d = np.searchsorted(ldp[:, l], r - l)
        if ldp[d, l] == r - l:
            ret += 2 ** d
            break
        if d > 0:
            d -= 1
        ret += 2 ** d
        l += ldp[d, l]
    return ret


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

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

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

X = np.array(X, dtype=int)
# rdp[d][i]: i番のホテルから(2^d)日で何個右までいけるか
rdp = np.zeros((N.bit_length(), N), dtype=int)
rdp[0] = np.searchsorted(X, X + L, side='right') - np.arange(N) - 1
for d in range(1, N.bit_length()):
    rdp[d] = rdp[d - 1] + rdp[d - 1][np.arange(N) + rdp[d - 1]]

X = -X[::-1]
# ldp[d][i]: i番のホテルから(2^d)日で何個左までいけるか
ldp = np.zeros((N.bit_length(), N), dtype=int)
ldp[0] = np.searchsorted(X, X + L, side='right') - np.arange(N) - 1
for d in range(1, N.bit_length()):
    ldp[d] = ldp[d - 1] + ldp[d - 1][np.arange(N) + ldp[d - 1]]

# print(rdp)
# print(ldp)


def solver(l, r):
    ret = 0
    while l < r:
        d = max(0, np.searchsorted(rdp[:, l], r - l) - 1)
        ret += 2 ** d
        l += rdp[d, l]
    return ret


def solvel(l, r):
    r = N - r - 1
    l = N - l - 1
    ret = 0
    while l < r:
        d = max(0, np.searchsorted(ldp[:, l], r - l) - 1)
        ret += 2 ** d
        l += ldp[d, l]
    return ret


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

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import*
r=range
n,*t=map(int,open(0).read().split())
m=2**16
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: Time Limit Exceeded

Solution code:
from bisect import*
r=range
n,*t=map(int,open(0).read().split())
m=2**17
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: Time Limit Exceeded

Solution code:
from bisect import bisect
inpl = lambda: list(map(int, input().split()))

N = int(input())
X = inpl()
L = int(input())
Q = int(input())
R = [[0]*(N) for k in range(17)]

for i in range(N):
    R[0][i] = bisect(X, X[i]+L) - 1

for k in range(16):
    for i in range(N):
        R[k+1][i] = R[k][R[k][i]]


def reach(a, d):
    O = format(d, "b").zfill(17)[::-1]
    for k in range(16, -1, -1):
        if O[k] == "1":
            a = R[k][a]
    return a


def bisearch(a, b):
    a, b = a-1, b-1
    if b < a:
        a, b = b, a
    OK = b-a
    NG = 0

    while abs(OK - NG) > 1:
        mid = (OK+NG)//2
        if reach(a, mid) >= b:
            OK = mid
        else:
            NG = mid
    return OK

print(*[bisearch(*inpl()) for _ in range(Q)], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from bisect import bisect
inpl = lambda: list(map(int, input().split()))

N = int(input())
X = inpl()
L = int(input())
Q = int(input())
R = {}

for i in range(N):
    R[(0, i)] = bisect(X, X[i]+L) - 1

for k in range(16):
    for i in range(N):
        R[(k+1, i)] = R[(k, R[(k, i)])]


def reach(a, d):
    O = format(d, "b").zfill(17)[::-1]
    for k in range(16, -1, -1):
        if O[k] == "1":
            a = R[(k, a)]
    return a


def bisearch(a, b):
    a, b = a-1, b-1
    if b < a:
        a, b = b, a
    OK = b-a
    NG = 0

    while abs(OK - NG) > 1:
        mid = (OK+NG)//2
        if reach(a, mid) >= b:
            OK = mid
        else:
            NG = mid
    return OK

print(*[bisearch(*inpl()) for _ in range(Q)], sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from bisect import bisect
inpl = lambda: list(map(int, input().split()))

N = int(input())
X = inpl()
L = int(input())
Q = int(input())
R = {}

for i in range(N):
    R[(0, i)] = bisect(X, X[i]+L) - 1

for k in range(17):
    for i in range(N):
        R[(k+1, i)] = R[(k, R[(k, i)])]


def reach(a, d):
    O = format(d, "b").zfill(18)[::-1]
    for k in range(17, -1, -1):
        if O[k] == "1":
            a = R[(k, a)]
    return a


def bisearch(a, b):
    a, b = a-1, b-1
    if b < a:
        a, b = b, a
    OK = 2**17
    NG = 0

    while abs(OK - NG) > 1:
        mid = (OK+NG)//2
        if reach(a, mid) >= b:
            OK = mid
        else:
            NG = mid
    return OK

print(*[bisearch(*inpl()) for _ in range(Q)], sep="\n")

Submission status: Time Limit Exceeded

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

import bisect
def calc_day(new_x):
  cur_idx = 0
  i = 0
  length = len(new_x)
  while cur_idx < length-1:
    cur_idx = bisect.bisect_right(new_x, new_x[cur_idx]+l)-1
    #print(cur_idx)
    i+=1
  return i
  
for i in range(q):
  if a[i] > b[i]:
    left = b[i]-1
    right = a[i]-1
    new_x = x[:]
  else:
    left = a[i]-1
    right = b[i]-1
    new_x = x[::-1]
    
  new_x = x[left:right+1]
  print(calc_day(new_x))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect
N=int(input())
X=[int(i) for i in input().split()]
L=int(input())
Q=int(input())
#T=[[int(i) for i in input().split()] for i in range(Q)]
T=[]
for i in range(Q):
    a,b=map(int,input().split())
    if a>b:
        a,b=b,a
    T.append((a-1,b-1))
F=[0]*N
for i in range(N):
    F[i]= bisect(X, X[i] + L) -1
for a,b in T:
    k=F[a]
    num=1
    while k<b:
        num+=1
        k=F[k]
    print(num)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right

N = int(input())
x = list(map(int, input().split()))
rx = list(sorted(map(lambda xx: -xx, x)))
L = int(input())
Q = int(input())
for _ in range(Q):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a < b:
        t = x[a]
        cnt = 0
        while True:
            t += L
            # print(t, x[b])
            cnt += 1
            i = bisect_right(x, t) - 1
            if i >= b:
                print(cnt)
                break
            else:
                t = x[i]
    else:
        t = rx[N - 1 - a]
        cnt = 0
        while True:
            t += L
            cnt += 1
            # print(rx, t, rx[N - 1 - b])
            i = bisect_right(rx, t) - 1
            if i >= N - 1 - b:
                print(cnt)
                break
            else:
                t = rx[i]

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N = int(input())
xx = inpl()
L = int(input())

K = N.bit_length()
db_r = [[0]*K for i in range(N)]
for i,x in enumerate(xx):
    ind = bisect.bisect_right(xx,x+L)
    db_r[i][0] = ind-1

for k in range(1,K):
    for i in range(N):
        db_r[i][k] = db_r[db_r[i][k-1]][k-1]

def check(a,b,d):
    L = d.bit_length()
    for k in range(L):
        if d & (1<<k):
            a = db_r[a][k]
    return a >= b

Q = int(input())
for i in range(Q):
    a,b = inpl()
    a -= 1
    b -= 1
    a,b = min(a,b),max(a,b)
    OK = N
    NG = 0
    while OK-NG>1:
        mid = (OK+NG)//2
        if check(a,b,mid): OK = mid
        else: NG = mid
    print(OK)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())

N = int(input())
xx = inpl()
L = int(input())
dd = []
for i,x in enumerate(xx):
    ind = bisect.bisect_right(xx,x+L)
    dd.append(ind-1)

Q = int(input())
for i in range(Q):
    a,b = inpl()
    a,b = min(a,b)-1,max(a,b)-1
    tmp = 0
    while a < b:
        a = dd[a]
        tmp += 1
    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
N = int(input())
xs = list(map(int,input().split()))
L = int(input())
Q = int(input())
qs = [tuple(map(lambda x:int(x)-1, input().split())) for i in range(Q)]

K = len(bin(N)) - 1
dp = [[None]*N for i in range(K)]
for i,x in enumerate(xs):
    dp[0][i] = bisect(xs, x+L) - 1
for k in range(K-1):
    for i in range(N):
        dp[k+1][i] = dp[k][dp[k][i]]

def enough(fr,to,n):
    now = fr
    bn = bin(n)
    ln = len(bn)-2
    for i,c in enumerate(bn[2:]):
        if c=='0': continue
        now = dp[ln-1-i][now]
        if now >= to:
            return True
    return False

ans = []
for a,b in qs:
    if a>b: a,b = b,a
    ok = N
    ng = 0
    while ok-ng > 1:
        m = (ok+ng)//2
        if enough(a,b,m):
            ok = m
        else:
            ng = m
    ans.append(ok)

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
N = int(input())
xs = list(map(int,input().split()))
L = int(input())
Q = int(input())
qs = [tuple(map(lambda x:int(x)-1, input().split())) for i in range(Q)]

K = len(bin(N)) - 1
dp = [[None]*N for i in range(K)]
for i,x in enumerate(xs):
    dp[0][i] = bisect(xs, x+L) - 1
for k in range(K-1):
    for i in range(N):
        dp[k+1][i] = dp[k][dp[k][i]]

def enough(fr,to,n):
    now = fr
    for k in reversed(range(K)):
        if n&(1<<k)==0: continue
        now = dp[k][now]
        if now >= to:
            return True
    return False

ans = []
for a,b in qs:
    if a>b: a,b = b,a
    ok = N
    ng = 0
    while ok-ng > 1:
        m = (ok+ng)//2
        if enough(a,b,m):
            ok = m
        else:
            ng = m
    ans.append(ok)

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect, bisect_left

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, input().split())
	if a > b:
		a, b = b, a
	print(search_2(a - 1, b - 1))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
X = [int(x) for x in input().split()]
L = int(input())
Q = int(input())
query = [[int(x) - 1 for x in input().split()] for i in range(Q)]
H = [0 for i in range(N)]
X.append(10 ** 9 + L + 1)
s = 0
t = 1
while t < N:
  while X[t] - X[s] <= L:
    t += 1
  H[s] = t - 1
  s += 1
  while s < N - 1:
    if X[t] - X[s] > L:
      H[s] = t - 1
      s += 1
    else:
      break
for q in query:
  a = min(q)
  b = max(q)
  d = 0
  while a < b:
    a = H[a]
    d += 1
  print(d)

Submission status: Time Limit Exceeded

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

K = 318

D = {}
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 (i, k) in D and (D[i, k], k) in D:
            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.get((a, k), N) < 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: Time 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: Time Limit Exceeded

Solution code:
# coding: utf-8
num_N = int(input())
l_pos = list(map(int, input().split()))
num_L = int(input())
num_Q = int(input())
l_que = [list(map(int, input().split())) for __ in range(num_Q)]


def solve(num_a, num_b):
    if num_b < num_a:
        num_a, num_b = num_b, num_a
    
    ans = 0
    from_pos = l_pos[num_a - 1]
    to_pos = l_pos[num_b - 1]
    now_pos = from_pos

    while now_pos + num_L < to_pos:
        for index, pos in enumerate(l_pos):
            if pos > now_pos + num_L:
                now_pos = l_pos[index - 1]
                ans += 1
                break
    
    ans += 1
    return ans

for que in l_que:
    print(solve(que[0], que[1]))

Submission status: Time Limit Exceeded

Solution code:
class Hotel:

    def query(self, N, x, L, Q, ab):

        x.append(pow(10, 9))

        for AB in ab:

            AB[0], AB[1] = min(AB[0], AB[1]), max(AB[0], AB[1])

            ans = 0
            current_hotel = AB[0]-1
            while current_hotel < AB[1]-1:

               
                l = L

                while x[current_hotel+1] - x[current_hotel] <= l:

                    l -= (x[current_hotel+1] - x[current_hotel])
                    current_hotel += 1

                ans += 1

            print ans


if __name__ == "__main__":

    N = input()
    x = [int(i) for i in raw_input().split()]
    L = input()
    Q = input()
    ab = [[int(j) for j in raw_input().split()] for i in range(Q)]

    abc = Hotel()
    abc.query(N, x, L, Q, ab)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_right
N=int(input())
x=[0]+list(map(int,input().split()))
L=int(input())
Q=int(input())
for _ in range(Q):
    a,b=sorted(map(int,input().split()))
    i=0
    while a<b:
        a=bisect_right(x,x[a]+L,a)-1
        i+=1
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from itertools import count
from bisect import bisect

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

j = bisect(X, X[0]+L)
for i in range(N):
  bound = X[i] + L
  try:
    while X[j] <= bound:
      j += 1
  except IndexError:
    X[i:] = [[] for _ in range(N-i)]
    n = i
    break
  X[i] = [j-1]

for d in count(0):
  for i in range(n):
    t = X[i][d]
    if t < n:
      X[i].append(X[t][d])
    else:
      n = i
      break
  if n == 0:
    break

result = [0]*Q

for i, (a,b) in enumerate(queries):
  if a > b:
    a,b = b,a

  p = bisect(X[a], b) - 1
  cnt = 0
  while p >= 0:
    cnt += 2**p
    a = X[a][p]
    p = bisect(X[a], b) - 1

  if a < b:
    cnt += 1

  result[i] = cnt

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

Submission status: Time Limit Exceeded

Solution code:
from itertools import count
from bisect import bisect

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

j = 0
for i in range(N):
  bound = X[i] + L
  try:
    while X[j] <= bound:
      j += 1
  except IndexError:
    X[i:] = [[] for _ in range(N-i)]
    n = i
    break
  X[i] = [j-1]

for d in count(0):
  for i in range(n):
    t = X[i][d]
    if t < n:
      X[i].append(X[t][d])
    else:
      n = i
      break
  if n == 0:
    break


Q = int(input())

for _ in range(Q):
  a, b = map(lambda s: int(s)-1, input().split())
  if a > b:
    a,b = b,a

  p = bisect(X[a], b) - 1
  cnt = 0
  while p >= 0:
    cnt += 2**p
    a = X[a][p]
    p = bisect(X[a], b) - 1

  if a < b:
    cnt += 1

  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from itertools import count
from bisect import bisect

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

j = 0
for i in range(N):
  bound = X[i] + L
  try:
    while X[j] <= bound:
      j += 1
  except IndexError:
    X[i:] = [[] for _ in range(N-i)]
    n = i
    break
  X[i] = [j-1]

for d in count(0):
  for i in range(n):
    t = X[i][d]
    if t < n:
      X[i].append(X[t][d])
    else:
      n = i
      break
  if n == 0:
    break

for a,b in queries:
  if a > b:
    a,b = b,a

  p = bisect(X[a], b) - 1
  cnt = 0
  while p >= 0:
    cnt += 2**p
    a = X[a][p]
    p = bisect(X[a], b) - 1

  if a < b:
    cnt += 1

  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from itertools import count
from bisect import bisect_right

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


j = 0
n = 0
for i in range(N):
  bound = X[i] + L
  try:
    while X[j] <= bound:
      j += 1
  except IndexError:
    X[i:] = [[] for _ in range(N-i)]
    n = i
    break
  X[i] = [j-1]

for d in count(0):
  for i in range(n):
    t = X[i][d]
    if t < n:
      X[i] += [X[t][d]]
    else:
      n = i
      break
  if n == 0:
    break

for a,b in queries:
  if a > b:
    a,b = b,a

  p = bisect_right(X[a], b) - 1
  cnt = 0
  while p >= 0:
    cnt += 2**p
    a = X[a][p]
    p = bisect_right(X[a], b) - 1

  if a < b:
    cnt += 1

  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
import math
import itertools
sys.setrecursionlimit(10000)

INF = float('inf')

# input macro
def i():
    return int(raw_input())
def ii():
    return map(int,raw_input().split(" "))
def s():
    return raw_input()
def ss():
    return raw_input().split(" ")
def slist():
    return list(raw_input())
#

def join(s):
    return ''.join(s)

#iterate macro
def piter(n,m):
    return itertools.permutations(n,m)
def citer(n,m):
    return itertools.combinations(n,m)

#modulo macro
def modc(a,b,m):
    c = 1
    for i in xrange(b):
        c = c * (a - i) % m
        c = c * modinv(i + 1,m) % m
    return c
 
def gcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
def modinv(a, m):
    (inv, q, gcd_val) = gcd(a, m)
    return inv % m

#bisect macro
def index(a, x):
    #Locate the leftmost value exactly equal to x
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    return -1

#memoize macro
def memoize(f):
    cache = {}
    def helper(*args):
        if args not in cache:
            cache[(args)] = f(*args)
        return cache[args]
    return helper

@memoize
def nck(a,b,m):
    b = min([a-b,b])
    if (b>a or b<0 or a<0):
        return 0
    elif a == 0:
        return 1
    return (nck(a-1,b-1,m)+nck(a-1,b,m)) % m

nh=zip([1,0,-1,0],[0,1,0,-1])

###########

n=i()
x=ii()
l=i()
q=i()
a,b=[0]*q,[0]*q
for j in range(q):
    a[j],b[j]=ii()

left=[0]*n
right=[0]*n

for (j,hotel) in enumerate(x):
    right[j]=bisect.bisect_right(x,hotel+l)-1
    left[j]=bisect.bisect_left(x,hotel-l)

for j in range(q):
    if a[j]<b[j]:
        cur=a[j]-1
        cnt=0
        while cur<b[j]-1:
            if x[cur]+l>=x[b[j]-1]:
                cnt+=1
                cur=b[j]-1
            else:
                cnt+=1
                cur=right[cur]
        print cnt
    else:
        cur=a[j]-1
        cnt=0
        while cur>b[j]-1:
            if x[cur]-l<=x[b[j]-1]:
                cnt+=1
                cur=b[j]-1
            else:
                cnt+=1
                cur=left[cur]
        print cnt

Submission status: Time Limit Exceeded

Solution code:
import bisect

n=int(raw_input())
x=map(int,raw_input().split())+[float('inf')]
l=int(raw_input())
q=int(raw_input())
for i in xrange(q):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    cnt=0
    if a<b:
        while a!=b:
            cnt+=1
            if x[a]+l==x[bisect.bisect_left(x,x[a]+l)]:
                a=bisect.bisect_left(x,x[a]+l)
            else:
                a=bisect.bisect_left(x,x[a]+l)-1
            if a>b:
                break
    else:
        while a!=b:
            cnt+=1
            if x[a]-l==x[bisect.bisect_left(x,x[a]-l)]:
                a=bisect.bisect_left(x,x[a]-l)
            else:
                a=bisect.bisect_left(x,x[a]-l)
            if a<b:
                break
    print(cnt)

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

j = 0
for i in range(N):
  bound = X[i] + L
  try:
    while X[j] <= bound:
      j += 1
  except IndexError:
    X[i:] = [N-1]*(N-i)
    break
  X[i] = j-1

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

Submission status: Time Limit Exceeded

Solution code:
import bisect

n=int(raw_input())
x=map(int,raw_input().split())
l=int(raw_input())
q=int(raw_input())
for i in xrange(q):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    cnt=0
    if a<b:
        while a!=b:
            cnt+=1
            if x[a]+l==x[bisect.bisect_left(x,x[a]+l)]:
                a=bisect.bisect_left(x,x[a]+l)
            else:
                a=bisect.bisect_left(x,x[a]+l)-1
            if a>b:
                break
    else:
        while a!=b:
            cnt+=1
            if x[a]-l==x[bisect.bisect_left(x,x[a]-l)]:
                a=bisect.bisect_left(x,x[a]-l)
            else:
                a=bisect.bisect_left(x,x[a]-l)
            if a<b:
                break
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(raw_input())
har = map(int , raw_input().split())
L = int(raw_input())
q = int(raw_input())

from collections import deque

def bfs(g, start):
    queue, enqueued = deque([(None, start)]), set([start])
    while queue:
        parent, n = queue.popleft()
        yield parent, n
        new = set(g[n]) - enqueued
        enqueued |= new
        queue.extend([(n, child) for child in new])
 
 
def s_p(g, start, end):
    parents = {}
    for parent, child in bfs(g, start):
        parents[child] = parent
        if child == end:
            revpath = [end]
            while True:
                parent = parents[child]
                revpath.append(parent)
                if parent == start:
                    break
                child = parent
            return list(reversed(revpath))
    return None # or raise appropriate exception

graph = {i:[] for i in xrange(n)}
for i in xrange(n):
    if i - 1 >= 0:graph[i].append(i-1)
    if i + 1 <= n-1:graph[i].append(i+1)
for i in xrange(q):
    a,b = map(int , raw_input().split())
    a-=1
    b-=1
    path = s_p(graph,a,b)
    ans = 0
    sm = 0
    #print path
    pre = har[path[0]]
    psm = 0
    cost = []
    pp = 0
    for ix in xrange(1,len(path)):
        sm += abs(har[path[ix]] - pre)
        psm += abs(har[path[ix]] - pre)
        pre = har[path[ix]]
        if sm > L:
          ans += 1
          sm -= pp
        if sm == L:
          sm = 0
          ans += 1
        cost.append(sm)
        pp = sm
    if sm > 0:
        ans += 1
    print ans