Submission #857407

---

Source Code Expand

#include <bits/stdc++.h>

#define x first
#define y second

using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;

int leap[20][100000];
int xs[100000],N,L,Q;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N;
	for (int i=0;i<N;i++) cin >> xs[i];
	int cr=N-1;
	cin >> L;
	for (int i=N-1;i>=0;i--) {
		while (xs[cr]-xs[i]>L) cr--;
		leap[0][i]=cr;
	}

	for (int i=1;i<20;i++) for (int j=0;j<N;j++) leap[i][j]=leap[i-1][leap[i-1][j]];

	cin >> Q;
	while (Q--) {
		int a,b;
		cin >> a >> b;
		a--;b--;
		if (a>b) swap(a,b);
		int sum=0,cur=a;
		for (int i=19;i>=0;i--) {
			if (leap[i][cur]<=b) {
				cur=leap[i][cur];
				sum|=1<<i;
			}
		}
		if (cur<b) sum++;
		/*while(cur!=b) {
			for (int i=0;;i++) {
				if (leap[i+1][cur]>b) {
					cur=leap[i][cur];
					sum+=1<<i;
					break;
				}
			}
		}*/

		cout << sum << '\n';
	}

}

Submission Info

Judge Result