Submission #855919

---

Source Code Expand

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}

#define N 100010
#define B 32

ll x[N], dp[B][N];
ll n, l, q;

int main(){
	cin>>n;
	rep(i, n) cin>>x[i];
	cin>>l>>q;
	x[n] = x[n-1]+l+1;
	{
		int lx = 0, rx = 0;
		while(lx < n){
			while(x[rx]-x[lx]<=l) rx++;
			dp[0][lx] = rx-1;
			lx++;
		}
		for(int i = 1; i < B; i++){
			for(int j = 0; j < n; j++){
				dp[i][j] = dp[i-1][dp[i-1][j]];
			}
		}
	}
	rep(_, q){
		int a, b;
		cin>>a>>b; a--; b--;
		if(a>b) swap(a, b);
		int lb = 0, ub = n-1; // (lb, ub]
		while(ub-lb>1){
			int md = (lb+ub+1)/2;
			int s = a;
			for(int j = 0; j < B; j++){
				if(1&(md>>j)) s = dp[j][s];
			}
			(b<=s?ub:lb)=md;
		}
		cout<<ub<<endl;
	}
	return 0;
}

Submission Info

Judge Result