Problem:


Score : 700 points

Problem Statement

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

Tak the traveler has the following two personal principles:

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

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

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

Constraints

2 \leq N \leq 10^5

1 \leq L \leq 10^9

1 \leq Q \leq 10^5

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

x_{i+1} - x_i \leq L

1 \leq a_j,b_j \leq N

a_j \neq b_j

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

Partial Score

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

Input

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

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

Output

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

Sample Input 1

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

Sample Output 1

4
2
1
2

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

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

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

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

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



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


Sample output:
4
2
1
2

Submission status: Wrong Answer

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

from bisect import bisect

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

main()

Submission status: Wrong Answer

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

from bisect import bisect

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

main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect
N=int(input())
X=[int(x) for x in input().split()]
L=int(input())
inf=float("inf")
X.append(X[-1]+L)
Table=[[inf]*18 for i in range(N)]
r=1
for i in range(N):
  if r<=N:
    while X[r]-X[i]<=L:
      r+=1
      if r>N:
        break
  Table[i][0]=r-1
for k in range(1,18):
  for i in range(N):
    if Table[i][k-1]==N:
      Table[i][k]=N
      continue
    Table[i][k]=Table[Table[i][k-1]][k-1]

Q=int(input())
for q in range(Q):
  a,b=map(int,input().split())
  a-=1
  b-=1
  ans=0
  if a>b:
    a,b=b,a
  while a<b:
    i=bisect(Table[a],b)-1
    ans+=2**i
    a=Table[a][i]
  
  print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect
N=int(input())
X=[int(x) for x in input().split()]
Xrev=list(map(lambda x:-x,X[::-1]))
L=int(input())
inf=float("inf")
X.append(X[-1]+L)
Xrev.append(Xrev[-1]+L)
Table=[[inf]*18 for i in range(N)]
Tablerev=[[inf]*18 for i in range(N)]
r=1
for i in range(N):
  if r<=N:
    while X[r]-X[i]<=L:
      r+=1
      if r>N:
        break
  Table[i][0]=r-1
for k in range(1,18):
  for i in range(N):
    if Table[i][k-1]==N:
      Table[i][k]=N
      continue
    Table[i][k]=Table[Table[i][k-1]][k-1]

r=1
for i in range(N):
  if r<=N:
    while Xrev[r]-Xrev[i]<=L:
      r+=1
      if r>N:
        break
  Tablerev[i][0]=r-1
for k in range(1,18):
  for i in range(N):
    if Tablerev[i][k-1]==N:
      Tablerev[i][k]=N
      continue
    Tablerev[i][k]=Tablerev[Tablerev[i][k-1]][k-1]
Q=int(input())
for q in range(Q):
  a,b=map(int,input().split())
  a-=1
  b-=1
  ans=0
  if a<=b:
    while a<b:
      i=bisect(Table[a],b)-1
      ans+=2**i
      a=Table[a][i]
      
  else:
    a,b=N-1-a,N-1-b
    while a<b:
      i=bisect(Tablerev[a],b)-1
      ans+=2**i
      a=Tablerev[a][i]
  print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
N=int(input())
X=[int(x) for x in input().split()]
Xrev=list(map(lambda x:-x,X[::-1]))
L=int(input())
inf=float("inf")
X.append(inf)
Xrev.append(inf)
Table=[[inf]*18 for i in range(N)]
Tablerev=[[inf]*18 for i in range(N)]
r=1
for i in range(N):
  while X[r]-X[i]<=L:
    r+=1
  Table[i][0]=r-1
for k in range(1,18):
  for i in range(N):
    Table[i][k]=Table[Table[i][k-1]][k-1]
    
r=1
for i in range(N):
  while Xrev[r]-Xrev[i]<=L:
    r+=1
  Tablerev[i][0]=r-1
for k in range(1,18):
  for i in range(N):
    Tablerev[i][k]=Tablerev[Table[i][k-1]][k-1]
Q=int(input())
for q in range(Q):
  a,b=map(int,input().split())
  a-=1
  b-=1
  ans=0
  if a<=b:
    while a<b:
      i=bisect_left(Table[a],b)
      ans+=2**i
      a=Table[a][i]
  else:
    a,b=N-1-a,N-1-b
    while a<b:
      i=bisect_left(Tablerev[a],b)
      ans+=2**i
      a=Tablerev[a][i]
  print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N = int(input())
X = list(map(int, input().split()))
L = int(input())

P = [[0] * N for i in range(30)]
for i in range(N):
    q = bisect_right(X, X[i] + L)
    P[0][i] = q - 1

for i in range(1, 30):
    for j in range(N):
        P[i][j] = P[i - 1][P[i - 1][j]]


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
    Y = X[b]
    num = 0
    for j in range(29, 0, -1):
        if X[P[j][a]] <= Y:
            Y = X[P[j][a]]
            num += 2 ** (j - 1)
    print(num + 1)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N = int(input())
X = list(map(int, input().split()))
L = int(input())

P = [[0] * N for i in range(30)]
for i in range(N):
    q = bisect_right(X, X[i] + L)
    P[0][i] = q - 1

for i in range(1, 30):
    for j in range(N):
        P[i][j] = P[i - 1][P[i - 1][j]]


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
    Y = X[b]
    num = 0
    for j in range(29, -1, -1):
        if X[P[j][a]] <= Y:
            Y -= X[P[j][a]]
            num += 2 ** j
        if Y <= 0:
            print(num)
            break

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N = int(input())
X = list(map(int, input().split()))
L = int(input())

P = [[0] * N for i in range(30)]
for i in range(N):
    q = bisect_right(X, X[i] + L)
    P[0][i] = q - 1

for i in range(1, 30):
    for j in range(N):
        P[i][j] = P[i - 1][P[i - 1][j]]

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
    Y = X[b]
    num = 0
    for j in range(29, -1, -1):
        if X[P[j][a]] <= Y:
            Y -= X[P[j][a]]
            a = P[j][a]
            num += 2 ** j
        if Y <= 0:
            print(num)
            break

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N = int(input())
X = list(map(int, input().split()))
L = int(input())

P = [[0] * N for i in range(30)]
for i in range(N):
    q = bisect_right(X, X[i] + L)
    P[0][i] = q - 1

for i in range(1, 30):
    for j in range(N):
        P[i][j] = P[i - 1][P[i - 1][j]]

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
    Y = X[b]
    num = 0
    for j in range(29, -1, -1):
        if X[P[j][a]] <= Y:
            Y -= X[P[j][a]]
            num += 2 ** j
        if Y <= 0:
            print(num)
            break

Submission status: Wrong Answer

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

V = [0]*N
ib = 0
for i in range(N):
    while X[i]-X[ib] > L:
        V[ib] = i-1
        ib += 1
while ib!=N-1:
    V[ib]=N-1
    ib += 1
dbl = [[0]*N for i in range(18)]
dbl[0]=V
for i in range(1, 18):
    for j in range(N):
        ii = dbl[i-1][j]
        if ii == 0:
            break
        dbl[i][j] = dbl[i-1][ii]
for i in range(Q):
    a, b = map(int, input().split())
    a, b = sorted([a, b])
    a-=1
    b-=1
    ind = a
    ans = 0
    for j in range(17, -1, -1):
        if dbl[j][ind]==0:
            continue
        if dbl[j][ind]>b:
            continue
        if dbl[j][ind]==b:
            ans |= 1<<j
            break
        else:
            ans |= 1<<j
            ind = dbl[j][ind]
    else:
        ans |= 1
    print(ans)

Submission status: Wrong Answer

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

V = [0]*N
ib = 0
for i in range(N):
    while X[i]-X[ib] > L:
        V[ib] = i-1
        ib += 1
while ib!=N-1:
    V[ib]=N-1
    ib += 1
S = [0]*N
h=N-1
cnt = 1
for i in range(N-2, -1, -1):
    if h==V[i]:
        S[i] = cnt
    else:
        cnt+=1
        h=i+1
        S[i] = cnt
for i in range(Q):
    a, b = map(int, input().split())
    a, b = sorted([a, b])
    print(min(1, S[a-1]-S[b-1]))

Submission status: Wrong Answer

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

V = [0]*N
ib = 0
for i in range(N):
    while X[i]-X[ib] > L:
        V[ib] = i-1
        ib += 1
while ib!=N-1:
    V[ib]=N-1
    ib += 1
S = [0]*N
h=N-1
cnt = 1
for i in range(N-2, -1, -1):
    if h==V[i]:
        S[i] = cnt
    else:
        cnt+=1
        h=i+1
        S[i] = cnt
for i in range(Q):
    a, b = map(int, input().split())
    a, b = sorted([a, b])
    print(S[a-1]-S[b-1])

Submission status: Wrong Answer

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

V = [0]*N
ib = 0
for i in range(N):
    while X[i]-X[ib] > L:
        V[ib] = i-1
        ib += 1
S = [0]*N
h=N-1
cnt = 0
for i in range(N-2, -1, -1):
    if h==V[i]:
        S[i] = cnt
    else:
        cnt+=1
        h=i+1
        S[i] = cnt
for i in range(Q):
    a, b = map(int, input().split())
    a, b = sorted([a, b])
    print(S[a-1]-S[b-1])

Submission status: Wrong Answer

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

V = [0]*N
ib = 0
for i in range(N):
    while X[i]-X[ib] > L:
        V[ib] = i-1
        ib += 1
S = [0]*N
h=N-1
cnt = 1
for i in range(N-2, -1, -1):
    if h==V[i]:
        S[i] = cnt
    else:
        cnt+=1
        h=i+1
        S[i] = cnt
for i in range(Q):
    a, b = map(int, input().split())
    a, b = sorted([a, b])
    print(S[a-1]-S[b-1])

Submission status: Wrong Answer

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]

print(db_r[0])

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: Wrong Answer

Solution code:
from bisect import bisect_right
from math import log
N = int(input())
X = list(map(int, input().split()))
L = int(input())


R = [[-1] * N for i in range(int(log(N, 2) + 1))]
# 1日で行けるところをにぶたんで求める
for i in range(N):
    R[0][i] = bisect_right(X, X[i] + L) - 1

# ダブリング
for k in range(1, len(R)):
    for i in range(N):
        R[k][i] = R[k-1][R[k-1][i]]

# にぶたんでクエリに答えていく
Q = int(input())
for q in range(Q):
    a, b = map(int, input().split())
    a, b = min(a, b)-1, max(a, b)-1

    ans = 0
    for k in range(len(R))[::-1]:
        if R[k][a] <= b:
            a = R[k][a]
            ans += 2 ** k
    print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
from itertools import accumulate
import heapq

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

G = [[] for i in range(N)]
for i in range(N):
    for j in range(i, bisect_right(X, X[i] + L)):
        G[i].append((j, 1))


def dijkstra(x):
    d = [float('inf')] * N
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


dist = dijkstra(0)
Q = int(input())
for q in range(Q):
    a, b = map(int, input().split())
    a, b = min(a, b) - 1, max(a, b) - 1
    print(max(1, dist[b] - dist[a]))

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
from itertools import accumulate
import heapq

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

G = [[] for i in range(N)]
for i in range(N):
    G[i].append((bisect_right(X, X[i] + L) - 1, 1))


def dijkstra(x):
    d = [float('inf')] * N
    d[x] = 0
    visited = {x}

    # d, u
    hq = [(0, x)]

    while hq:
        u = heapq.heappop(hq)[1]
        visited.add(u)

        for node, cost in G[u]:
            if (node not in visited) and d[node] > d[u] + cost:
                d[node] = d[u] + cost
                heapq.heappush(hq, (d[u]+cost, node))
    return d


dist = dijkstra(0)
for i in range(1, N):
    if dist[i] == float('inf'):
        dist[i] = dist[i-1] + 1

Q = int(input())
for q in range(Q):
    a, b = map(int, input().split())
    a, b = min(a, b) - 1, max(a, b) - 1
    print(max(1, dist[b] - dist[a]))

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    xs = [int(c) for c in input().split()]
    l = int(input())

    xs.append(10 ** 17)
    nexts = list(range(n))
    for fr in range(n):
        p, q = fr, n
        while q - p > 1:
            m = (p + q) // 2
            if xs[m] - xs[fr] <= l:
                p = m
            else:
                q = m
        nexts[fr] = p

    doubling = [nexts]
    for _ in range(20):
        base = doubling[-1]
        nexts = [base[base_next] for base_next in base]
        doubling.append(nexts)

    def query(fr, to):
        if fr >= to:
            return 0
        p, q = 0, 20
        while q - p > 1:
            m = (p + q) // 2
            if doubling[m][fr] > to:
                q = m
            else:
                p = m

        return query(doubling[p][fr], to) + 2 ** p

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

        print(query(a, b))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

# dp[k][i] = i番目のホテルからk ** 2日以内に到達可能な最右のホテル番号
dp = [[0] * (num_N + 1) for __ in range(num_N + 1)]
for i in range(1, num_N + 1):
    max_ind = 0
    for ind, pos in enumerate(l_pos):
        if l_pos[i - 1] + num_L >= pos:
            max_ind = max(max_ind, ind)

    dp[0][i] = max_ind + 1

k = 0
while True:
    for i in range(1, num_N + 1):
        dp[k + 1][i] = dp[k][dp[k][i]]
    if dp[k + 1][1] == dp[k + 1][num_N]:
        break
    k += 1


def solve(num_a, num_b):
    if num_a > num_b:
        num_a, num_b = num_b, num_a

    num_k = 0
    while True:
        if dp[num_k][num_a] >= num_b:
            break
        
        num_k += 1
    
    return int(2 ** num_k)

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

Submission status: Wrong Answer

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)

###########

n=i()
x=ii()
l=i()
q=i()
a,b=[0]*q,[0]*q
for j in range(q):
    aa,bb=ii()
    a[j],b[j]=min(aa,bb)-1,max(aa,bb)-1
table=[[0 for i in range(n)] for j in range(32)]


for k in range(n):
    table[0][k]=bisect.bisect_right(x,x[k]+l)-1
for j in range(1,32):
    for k in range(n):
        table[j][k]=table[j-1][table[j-1][k]]
print table
for j in range(q):
    day=0
    cur=a[j]
    for k in reversed(range(32)):
        if table[k][cur]<b[j]:
            day+=2**k
            cur=table[k][cur]
    print day+1

Submission status: Wrong Answer

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)

###########

n=i()
x=ii()
l=i()
q=i()
a,b=[0]*q,[0]*q
for j in range(q):
    aa,bb=ii()
    a[j],b[j]=min(aa,bb)-1,max(aa,bb)-1
table=[[0 for i in range(n)] for j in range(32)]


for k in range(n):
    table[0][k]=bisect.bisect_right(x,x[k]+l)-1
for j in range(1,32):
    for k in range(n):
        table[j][k]=table[j-1][table[j-1][k]]
for j in range(q):
    day=0
    cur=a[j]
    for k in reversed(range(32)):
        if table[k][cur]<=b[j]:
            day+=2**k
            cur=table[k][cur]
    print day

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right,bisect_left
N=int(input())
x=[0]+list(map(int,input().split()))
L=int(input())
Q=int(input())
y=[None]*(N+1)
for _ in range(Q):
    a,b=sorted(map(int,input().split()))
    c=0
    p=[a]
    while a<b:
        if y[a]:
            i=bisect_left(y[a],a)
            j=bisect_left(y[a],b)
            c+=min(j,len(y[a])-1)-i
            a=y[a][-1]
            continue
        y[a]=p
        c+=1
        a=bisect_right(x,x[a]+L,a)-1
        p.append(a)
    print(c)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right,bisect_left
N=int(input())
x=[0]+list(map(int,input().split()))
L=int(input())
Q=int(input())
y=[None]*(N+1)
for _ in range(Q):
    a,b=sorted(map(int,input().split()))
    c=0
    p=[a]
    while a<b:
        if y[a]:
            i=bisect_left(y[a],a)
            j=bisect_left(y[a],b)
            c+=min(j,len(y[a])-1)-i
            a=y[a][-1]
            continue
        y[a]=p
        c+=1
        a=bisect_right(x,x[a]+L,a)-1
        p.append(a)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right,bisect_left
N=int(input())
x=[0]+list(map(int,input().split()))
L=int(input())
Q=int(input())
y=[None]*(N+1)
for _ in range(Q):
    a,b=sorted(map(int,input().split()))
    c=0
    p=[a]
    while a<b:
        if y[a]:
            i=bisect_left(y[a],a)
            j=bisect_left(y[a],b)
            a=y[a][-1]
            c+=j-i
            continue
        y[a]=p
        a=bisect_right(x,x[a]+L,a)-1
        p.append(a)
        c+=1
    print(c)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right,bisect_left
N=int(input())
x=[0]+list(map(int,input().split()))
L=int(input())
Q=int(input())
y=[None]*(N+1)
for _ in range(Q):
    a,b=sorted(map(int,input().split()))
    c=0
    p=[]
    while a<b:
        if y[a]:
            i=bisect_left(y[a],a)
            j=bisect_left(y[a],b)
            c+=j-i
            if j==len(y[a]):
                break
            a=y[a][j]
            continue
        c+=1
        p+=[a]
        y[a]=p
        a=bisect_right(x,x[a]+L,a)-1
    print(c)

Submission status: Wrong Answer

Solution code:
import bisect

n=int(raw_input())
x=map(int,raw_input().split())+[float('inf')]
l=int(raw_input())
q=int(raw_input())
r=[[0]*20 for _ in xrange(n)]

for i in xrange(n):
    if x[i]+l==x[bisect.bisect_left(x,x[i]+l)]:
        r[i][0]=bisect.bisect_left(x,x[i]+l)
    else:
        r[i][0]=bisect.bisect_left(x,x[i]+l)-1

for k in xrange(19):
    for i in xrange(n):
        r[i][k+1]=r[r[i][k]][k]

for i in xrange(q):
    a,b=map(int,raw_input().split())
    a-=1
    b-=1
    if a>b:
        a,b=b,a
    while 1:
        #print bisect.bisect_left(r[a],b),r[a]
        if b==r[a][bisect.bisect_left(r[a],b)]:
            print(1<<bisect.bisect_left(r[a],b))
            break
        else:
            a=r[a][bisect.bisect_left(r[a],b)-1]

Submission status: Wrong Answer

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)
print right
print left

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: Wrong Answer

Solution code:
import bisect

n=int(raw_input())
if n>10**3:
    quit()
x=map(int,raw_input().split())+[float('inf')]
l=int(raw_input())
q=int(raw_input())
if q>10**3:
    quit()
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: Wrong Answer

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):
  print('loop')
  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: Wrong Answer

Solution code:
#!/usr/bin/env pypy3


MAX_N = 10 ** 3
MAX_Q = 10 ** 3


def answer_query(ds, l, a, b):
    if a > b:
        a, b = b, a
    allowed_dist = l
    ans = 1
    for d in ds[a:b]:
        if allowed_dist >= d:
            allowed_dist -= d
        else:
            allowed_dist = l - d
            ans += 1
    return ans


def main():
    n = int(input())
    assert n <= MAX_N
    xs = list(map(int, input().split()))
    ds = [xj - xi for xi, xj in zip(xs[:-1], xs[1:])]
    print(ds)
    l = int(input())
    q = int(input())
    assert q <= MAX_Q
    for _ in range(q):
        a, b = map(lambda x: int(x) - 1, input().split())
        print(answer_query(ds, l, a, b))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)  # 変更
from bisect import bisect_left,bisect

n = int(input())
x = list(map(int,input().split()))
L = int(input())
t = n.bit_length()
prv = [n-1] * n
for i in range(n):
    prv[i] = bisect(x,x[i]+L) - 1
kprv = [prv]
S = prv
for i in range(t-1):
    kar = [n-1] * n
    for j in range(n):
        kar[j] = S[S[j]]
    kprv.append(kar)
    S = kar

q = int(input())
for _ in range(q):
    a , b = map(lambda x:int(x)-1,input().split())
    if a > b:
        a , b = b , a
    lef = 0
    rig = n-1
    while rig - lef > 1:
        mid = (rig+lef)//2
        p = mid.bit_length()
        now = a
        for i in range(p):
            if (mid>>i) & 1 == 1:
                now = kprv[i][now]
        if now >= b:
            rig = mid
        elif now < b:
            lef = mid
    print(rig)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10 ** 6)
    from bisect import bisect_left,bisect
    n = int(input())
    x = list(map(int,input().split()))
    t = n.bit_length()

    kprv = [[10**10 for i in range(t+1)] for j in range(n)]
    for i in range(t):
        for j in range(n):
            if j + pow(2,i) > n-1:
                break
            kprv[j][i] = x[j+pow(2,i)] - x[j]

    L = int(input())
    q = int(input())

    for _ in range(q):
        a , b = map(lambda x:int(x)-1,input().split())
        cou = 0
        if a > b:
            a , b = b , a
        now = a
        while now < b:
            cou += 1
            p = L
            while True:
                nex = bisect(kprv[now],p)
                if nex == 0:
                    break
                else:
                    p -= kprv[now][nex-1]
                    now += pow(2,nex-1)
        print(cou)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10 ** 6)
    from bisect import bisect_left,bisect
    n = int(input())
    x = list(map(int,input().split()))
    t = n.bit_length()

    kprv = [[10**10 for i in range(t+1)] for j in range(n)]
    for i in range(t):
        for j in range(n):
            if j + pow(2,i) > n-1:
                break
            kprv[j][i] = x[j+2**i] - x[j]

    L = int(input())
    q = int(input())

    for _ in range(q):
        a , b = map(lambda x:int(x)-1,input().split())
        cou = 0
        if a > b:
            a , b = b , a
        now = a
        while now < b:
            cou += 1
            p = L
            while True:
                nex = bisect(kprv[now],p)
                if nex == 0:
                    break
                else:
                    p -= kprv[now][nex-1]
                    now += pow(2,nex-1)
        print(cou)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)  # 変更

from bisect import bisect_left,bisect
n = int(input())
x = list(map(int,input().split()))
t = n.bit_length()
kprv = [[10**10 for i in range(t+1)] for j in range(n)]
for i in range(t):
    for j in range(n):
        if j + pow(2,i) > n-1:
            break
        kprv[j][i] = x[j+2**i] - x[j]

L = int(input())
q = int(input())

for _ in range(q):
    a , b = map(lambda x:int(x)-1,input().split())
    cou = 0
    if a > b:
        a , b = b , a
    now = a
    while now < b:
        cou += 1
        p = L
        while True:
            nex = bisect(kprv[now],p)
            if nex == 0:
                break
            else:
                p -= kprv[now][nex-1]
                now += pow(2,nex-1)
    print(cou)