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
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


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

from bisect import bisect_right

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


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


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

Submission status: Wrong Answer

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


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

from bisect import bisect_right

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


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


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

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

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


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


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

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

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

Submission status: Wrong Answer

Solution code:
import sys,bisect

input=sys.stdin.readline

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

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

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

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

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

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


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

Submission status: Wrong Answer

Solution code:
import sys,bisect

input=sys.stdin.readline

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

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

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

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

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

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

print(backdoubling[0])
print(backdoubling[1])

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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 ub == 0 or dist[x1][ub] == x2:
            return x2, 2 ** ub
        else:
            return dist[x1][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: Wrong Answer

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

from functools import lru_cache

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)

    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
        t = 1

        bisect = Bisect(lambda x: f(a, x))
        i = bisect.bisect_right(b, 0, len(X)+1) - 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: Wrong Answer

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


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

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

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

Submission status: Wrong Answer

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


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

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

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

Submission status: Wrong Answer

Solution code:
import math
from bisect import bisect_left, bisect_right

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

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

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

for a, b in Y:
    a -= 1
    b -= 1
    if a > b:
        a, b = b, a
    i = bisect_left([parent[j][a] for j in range(LOGN + 1)], b)
    print(2 ** i)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    x = LI()
    f = [[] for i in range(n)]
    l = I()
    for i in range(n):
        xi = x[i]
        j = bisect.bisect_right(x,l+xi)-1
        f[i].append(j)
    h = int(math.log(n,2))+1
    for j in range(h-1):
        for i in range(n):
            f[i].append(f[f[i][j]][j])
    q = I()
    for _ in range(q):
        a,b = LI()
        a -= 1
        b -= 1
        if b < a:
            a,b = b,a
        ans = 0
        if f[a][0] >= b:
            print(1)
            continue
        for i in range(h)[::-1]:
            if f[a][i] <= b:
                a = f[a][i]
                ans += 1<<i
        print(ans)
    return

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

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    x = LI()
    f = [[] for i in range(n)]
    l = I()
    for i in range(n):
        xi = x[i]
        j = bisect.bisect_right(x,l+xi)-1
        f[i].append(j)
    h = int(math.log(n,2))+1
    for j in range(h-1):
        for i in range(n):
            f[i].append(f[f[i][j]][j])
    q = I()
    for _ in range(q):
        a,b = LI()
        a -= 1
        b -= 1
        if b < a:
            a,b = b,a
        ans = 0
        for i in range(h)[::-1]:
            if f[a][i] <= b:
                a = f[a][i]
                ans += 1<<i
        print(ans)
    return

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

Submission status: Wrong Answer

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)]
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+1)]
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 or group[graph[x]]:
        break
      x = graph[x]

q = int(input())
for _ in range(q):
  l,r = map(int,input().split())
  if l>r:
    l,r = r,l
  xl = group[l]
  xr = group[r]
  if xl == xr:
    yl = bisect.bisect_left(row[xl],l)
    yr = bisect.bisect_left(row[xr],r)
  elif xl < xr:
    yl = bisect.bisect_left(row[xl],l)
    yr = bisect.bisect_left(row[xl],r)
  elif xl > xr:
    yl = bisect.bisect_right(row[xr],l)
    yr = bisect.bisect_right(row[xr],r)
  print(yr-yl)

Submission status: Wrong Answer

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

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

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

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)
  if x == i:
    continue
  graph[i+1] = x
group = [0]*(n+1)
row = [[] for i in range(n)]
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(r-l)

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect

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

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
from bisect import bisect

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

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

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

print(*buf)

Submission status: Wrong Answer

Solution code:
import bisect

def wantp(p,day):

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

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

        #print (day,i)

    return p


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

able = []

for i in range(N):

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


db = [able]

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

    new = []

    for i in range(N):

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

    db.append(new)


Q = int(input())

for loop in range(Q):

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

    l = 0
    r = len(db)

    while r-l != 1:

        m = (l+r) // 2

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

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

    print (r)

Submission status: Wrong Answer

Solution code:
import bisect

def wantp(p,day):

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

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

    return p

N = int(input())

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

L = int(input())

able = []

for i in range(N):

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

#print (able)

db = [able]

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

    new = []

    for i in range(N):

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

    db.append(new)

#print (db)

Q = int(input())

for loop in range(Q):

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

    l = 0
    r = N

    while r-l != 1:

        m = (l+r) // 2

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

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

    print (r)

Submission status: Wrong Answer

Solution code:
import bisect

def wantp(p,day,db):

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

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

    return p

N = int(input())

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

L = int(input())

able = []

for i in range(N):

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

#print (able)

db = [able]

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

    new = []

    for i in range(N):

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

    db.append(new)

db1 = []
for i in db:
    db1.append(i)

for i in range(N):
    x[i] = x[-1] - x[i]
x.reverse()
#print (x)

able = []
for i in range(N):
    able.append(bisect.bisect_right(x,x[i] + L) - 1)
db = [able]
while min(db[-1]) != N-1:
    new = []
    for i in range(N):
        new.append(db[-1][db[-1][i]])
    db.append(new)
db2 = db
#print (db2)


Q = int(input())

for loop in range(Q):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    if a < b:

        l = 0
        r = N+1

        while r-l != 1:

            m = (l+r) // 2

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

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

        print (r)

    else:
        a = N-1-a
        b = N-1-b

        l = 0
        r = N+1

        while r-l != 1:

            m = (l+r) // 2

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

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

        print (r)

Submission status: Wrong Answer

Solution code:
import bisect

def wantp(p,day):

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

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

    return p

N = int(input())

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

L = int(input())

able = []

for i in range(N):

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

#print (able)

db = [able]

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

    new = []

    for i in range(N):

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

    db.append(new)

#print (db)

Q = int(input())

for loop in range(Q):

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

    l = 0
    r = N+1

    while r-l != 1:

        m = (l+r) // 2

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

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

    print (r)