Submission #856539

---

Source Code Expand

//It’s never too late to become what you might have been....
 #include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define inf 1000000000000
#define mod 1000000007
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define S second
#define F first
#define boost1 ios::sync_with_stdio(false);
#define boost2 cin.tie(0);
#define mem(a,val) memset(a,val,sizeof a)
#define endl "\n"
#define maxn 100001

ll a[maxn],block[maxn],block_no,store[maxn],sz=400,cnt[maxn],nxt[maxn];
int main()
{
	boost1;boost2;	
	ll i,j,n,q,x,y,l,r,L,curl,ind,ctr=0;
	cin>>n;
	for(i=1;i<=n;i++)
	cin>>a[i];
	cin>>L;
	for(i=1;i<=n;i++)
	{
		block_no++;
		for(j=i;j<=min(n,i+sz-1);j++)
		block[j]=i;
		i=i+sz-1;
	}
	for(i=1;i<=n;i++)
	{
		x=a[i]+L;
		if(a[n]<=a[i]+L)
		store[i]=n;
		else
		{
			ind=lower_bound(a+1,a+n+1,x)-a;
			if(a[ind]>a[i]+L)
			ind--;
			store[i]=ind;
		}	
	}
	for(i=n+1;i<=n+500;i++)
	store[i]=n;
	for(i=n;i>=1;i--)
	{
		x=a[i]+L;	
		ind=store[i];
		if(block[ind]!=block[i])
		{
			cnt[i]=1;
			nxt[i]=ind;
		}
		else
		{
			cnt[i]=cnt[ind]+1;
			nxt[i]=nxt[ind];
		}
	}
	cin>>q;
	while(q--)
	{
		cin>>l>>r;
		if(l>r)
		swap(l,r);
		ctr=0;
		curl=l;
		if(block[l]!=block[r])
		{
			curl=l;
			ctr=cnt[curl];
			curl=nxt[curl];
		}
		while(1)
		{
			if(block[curl]==block[r])
			break;
			ctr+=cnt[curl];
			curl=nxt[curl];
		}
		while(1)
		{
			if(curl>=r)
			{
				cout<<ctr<<endl;
				break;
			}
			x=a[curl]+L;
			curl=store[curl];
			ctr++;
		}
	}
	return 0;
}

Submission Info

Judge Result