Submission #3776405

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
const int INF = 1000000009;
typedef pair<int, int> pii;

int N, L, Q, x[100005], to[100005][20];

signed main()
{
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> x[i];
    }
    for(int i = 0; i < N + 1; i++){
        for(int j = 0; j < 20; j++){
            to[i][j] = INF;
        }
    }
    cin >> L >> Q;
    int cnt = 0;
    for(int i = 0; i < N; i++){
        while(cnt < N && x[cnt] - x[i] <= L)cnt++;
        to[0][i] = cnt - 1;
    }

    for(int i = 1; i < 20; i++){
        for(int j = 0; j < N; j++){
            to[i][j] = to[i - 1][to[i - 1][j]];
        }
    }
    while(Q--){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        if(a > b)swap(a, b);
        int ans = 1;
        for(int i = 19; i >= 0; i--){
            if(to[i][a] < b){
                a = to[i][a];
                ans += (1 << i);
            }
        }
        cout << ans << endl;
    }


    return 0;
}
/*


*/

Submission Info

Judge Result