# HackerEarth Travelling between cities solution

In this HackerEarth Travelling between cities problem solution, You are given positions of N cities situated on the X-axis. The position of the ith city is denoted by array value Location[i]. You have a bike that can travel at most K unit distance once the tank is full and each city has a fuel pump. You can assume that once the bike reaches a city its tank is again filled up completely. Now you have to answer Q queries where each query is of the following form.

L R X:- Find the number of cities lying in the index range [L, R] that you can reach from the city at index X.

## HackerEarth Travelling between cities problem solution.

`#include <bits/stdc++.h>#define sflld(n) scanf("%lld",&n)#define sfulld(n) scanf("%llu",&n)#define sfd(n) scanf("%d",&n)#define sfld(n) scanf("%ld",&n)#define sfs(n) scanf("%s",&n)#define ll long long#define s(t) int t; while(t--)#define ull unsigned long long int#define pflld(n) printf("%lld\n",n)#define pfd(n) printf("%d\n",n)#define pfld(n) printf("%ld\n",n)#define lt 2*idx#define rt 2*idx+1#define f(i,k,n) for(i=k;i<n;i++)#define MAXN 100050#define P pair<int,int>using namespace std;int cap[100050];P arr[MAXN];map<int,vector<int> > mp;int main(){    int t;    sfd(t);    while(t--)    {        int n,k,p,i;        sfd(n);        sfd(k);        sfd(p);        mp.clear();        assert(1<=n&&n<=50000);        assert(1<=k&&k<=1000000);        assert(1<=p&&p<=50000);        f(i,1,n+1)        {            int x;            sfd(x);            arr[i]=make_pair(x,i);            assert(1<=x&&x<=1000000000);        }        sort(arr+1,arr+n+1);        cap[arr[n].second]=arr[n].first+k;        i=n-1;        while(i>0)        {            if(arr[i+1].first-arr[i].first<=k)            {                cap[arr[i].second]=cap[arr[i+1].second];            }            else                cap[arr[i].second]=arr[i].first+k;                i--;        }        //build(1,1,n);        f(i,1,n+1)        {            mp[cap[i]].push_back(i);        }        while(p--)        {            int l,r,x;            sfd(l);            sfd(r);            sfd(x);            assert(1<=l&&l<=r&&r<=n);            assert(1<=x&&x<=n);            int k=cap[x];            pfd(upper_bound(mp[k].begin(),mp[k].end(),r)-lower_bound(mp[k].begin(),mp[k].end(),l));        }    }    return 0;}`

### Second solution

`#include<bits/stdc++.h>#define LL long long int#define M 1000000007#define endl "\n"#define eps 0.00000001LL pow(LL a,LL b,LL m){LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}using namespace std;int comp[10000001];int a[1000001];vector<int> st[1000001];int main()    {        ios_base::sync_with_stdio(0);        int t;        cin >> t;        while(t--)            {                vector<pair<int,int> > v;                int n , k , q;                cin >> n >> k >> q;                for(int i = 1; i <= n; i++)                    {                        cin >> a[i];                        v.push_back(make_pair(a[i] , i));                    }                sort(v.begin() , v.end());                int idx = 1;                comp[v[0].second] = 1;                st[1].push_back(v[0].second);                for(int i = 1; i < v.size(); i++)                    {                        if(v[i].first - v[i - 1].first <= k)                            {                                comp[v[i].second] = comp[v[i - 1].second];                            }                        else                                comp[v[i].second] = ++idx;                        st[comp[v[i].second]].push_back(v[i].second);                    }                for(int i = 1; i <= idx; i++)                    sort(st[i].begin() , st[i].end());                while(q--)                    {                        int l , r , x;                        cin >> l >> r >> x;                        int id = comp[x];                        cout << upper_bound(st[id].begin() , st[id].end() , r) - upper_bound(st[id].begin() , st[id].end() , l - 1) << endl;;                    }                for(int i = 1; i <= idx; i++)                    {                        st[i].clear();                    }                v.clear();            }    }`