Submission #3769066

---

Source Code Expand

#include <iostream>
#include <algorithm>

using namespace std;

#define REP(i,n) for (int i = 0; i < n; i++)

const int MAX = 1e5+10;

int N, L, Q;
int x[MAX];
int dp[MAX][22];

int main() {

  cin >> N;
  REP (i, N) cin >> x[i+1];
  cin >> L >> Q;

  REP (i, 20) dp[N+1][i] = dp[N][i] = N+1;
  for (int i = N-1; i >= 1; i--) {
    int lo = i+1, hi = N+1;
    while (hi-lo > 1) {
      int mid = (hi+lo)/2;
      if (x[mid]-x[i] <= L) lo = mid;
      else hi = mid;
    }
    dp[i][0] = lo;
    for (int j = 1; j < 20; j++) {
      dp[i][j] = dp[ dp[i][j-1] ][j-1];
    }
  }

  REP (q, Q) {
    int a, b;
    cin >> a >> b;
    if (a > b) swap(a, b);

    int ans = 0;
    for (int i = 19; i >= 0; i--) {
      if (dp[a][i] <= b) {
        ans += (1<<i);
        a = dp[a][i];
      }
    }
    cout << ans << endl;
  }

}

Submission Info

Judge Result