Submission #856243

---

Source Code Expand

#include<iostream>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<string.h>
#include<queue>
#include<stack>
#include<climits>
#include<cmath>
using namespace std;

int main(){
    int n,l,q;
    int a[100002];
    int b[100002];
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    cin>>l>>q;
    for(int i=0;i<n;i++){
        auto au = lower_bound(a, a+n, a[i]+l);
        if(*au - a[i]>l){
            au--;
        }
        b[i]=au-a;
    }
    for(int i=0;i<q;i++){
        int x,y;
        cin>>x>>y;
        x--,y--;
        if(x>y)swap(x,y);
        int ret=0;
        while(x<y){
            x=b[x];
            ret++;
        }
        cout<<ret<<endl;
    }
    return 0;
}

Submission Info

Judge Result