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: Runtime Error

Solution code:
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <cstdio>
#include <cctype>
#include <string>
#include <cstring>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std ;

#define rep(i, a, b) for (int (i)=(a);(i)<=(b);(i)++)
#define Rep(i, a, b) for (int (i)=(a)-1;(i)<(b);(i)++)
#define REP(i, a, b) for (int (i)=(a);(i)>=(b);(i)--)
#define reg(i, x) for (int (i)=head[x];(i);i=e[i].next)
#define clr(a) memset(a,0,sizeof(a))
#define Sort(a, len) sort(a + 1, a + len + 1)
#define Sort2(a, len, cmp) sort(a + 1, a + len + 1, cmp)
#define ass(a, sum) memset(a, sum, sizeof(a))

#define ull unsigned long long
#define ll long long
#define ls ((rt) << 1)
#define rs ((rt) << 1 | 1)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define endl '\n'
#define Pii pair<int, int>

const int N = 25000 ;
const int iinf = INT_MAX/2 ;
const ll linf = LLONG_MAX/2 ;
const int MOD = 1e9+7 ;

inline int read(){
    int X = 0,w = 0 ;
	char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-';ch = getchar();}
    while(isdigit(ch)) X = (X<<3) + (X<<1) + (ch ^ 48),ch = getchar();
    return w ? -X : X;
}

void write(int x){
     if(x < 0) putchar('-'),x = -x;
     if(x > 9) write(x / 10);
     putchar(x%10 + '0');
}

void print(int x) {
	cout << x << endl ;
	exit(0) ;
}

void douout(double x){
	 printf("%lf\n", x + 0.0000000001) ;
}

ll n,m,x,y,k,num[110],h,dp[N],cnt,d2[N],ans;
int main(){
	ll i,j;
	cin>>n>>k;
	for(i=1;i<=n;i++) scanf("%lld",&num[i]); 
	sort(num+1,num+n+1);
	dp[0]=d2[0]=1;
	for(i=1;num[i]<k&&i<=n;i++){
		num[i]=k-num[i];
		for(j=3000;j>=num[i];j--) dp[j]+=dp[j-num[i]]; 
	}
	for(;num[i]==k&&i<=n;i++) cnt++;
	for(;i<=n;i++){
		num[i]-=k;
		for(j=3000;j>=num[i];j--) d2[j]+=d2[j-num[i]]; 
	}
	for(i=0;i<=3000;i++) ans+=dp[i]*d2[i]*(1ll << cnt); 
	cout<<ans-1;
}

/*
写代码时请注意：
	1.是否要开Long Long？数组边界处理好了么？
	2.特殊情况处理好了么？
	3.做一些总比不做好。
	4.最大值和最小值问题可不可以用二分答案？
	5.有没有贪心策略？否则能不能dp？
	6.实数精度有没有处理？
*/

Submission status: Runtime Error

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
def travel(a, b, k):
  if H[a] >= b:
    return k + 1
  else:
    return travel(H[a], b, k + 1)
for q in query:
  a = min(q)
  b = max(q)
  print(travel(a, b, 0))

Submission status: Runtime Error

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: Runtime Error

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

K = N.bit_length()

D = [[-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
v = 2
for k in range(K):
    for i in range(N-v):
        if i + v < N and len(D[D[i][k]]) == k+1:
            D[i].append(D[D[i][k]][k])
    v <<= 1
def solve(a, b):
    if not a < b:
        a, b = b, a
    res = 1
    v = 2**K
    for k in range(K, -1, -1):
        if a + v < N-1 and D[a][k] < b:
            a = D[a][k]
            res += v
        v >>= 1
    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: Runtime Error

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=(day+2**k)%mod
            cur=table[k][cur]
    print day

Submission status: Runtime Error

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