Submission #3774413

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000009
#define pb push_back

int N, L, Q, x[100005];
vector<int> G[100005], X;
map<int, int> mp;
int d[100005];

signed main()
{
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> x[i];
        mp[x[i]] = i;
        X.pb(-x[i]);
        d[i] = INF;
        if(i < N - 1){
            G[i].pb(i + 1);
        }
    }
    sort(X.begin(), X.end());
    cin >> L;
    for(int i = 0; i < N - 1; i++){
        int res = mp[-*lower_bound(X.begin(), X.end(), -x[i] - L)];
        if(0 <= res && res < N && i < res){
            G[i].pb(res);
        }
    }
    queue<int> que;
    que.push(0ll);
    d[0] = 0ll;
    while(!que.empty()){
        int v = que.front();
        que.pop();
        for(int i = 0; i < (int)G[v].size(); i++){
            int to = G[v][i];
            if(d[to] == INF){
                que.push(to);
                d[to] = d[v] + 1ll;
            }
        }
    }
    for(int i = N - 2; i >= 0; i--){
        if(d[i] > d[i + 1]){
            d[i] = d[i + 1];
        }
    }
    cin >> Q;
    for(int i = 0; i < Q; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        if(a < b)swap(a, b);
        cout << max(d[a] - d[b], 1ll) << endl;
    }

    return 0;
}

Submission Info

Judge Result