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("%lldn",n)
#define pfd(n) printf("%dn",n)
#define pfld(n) printf("%ldn",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.00000001
LL 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();
            }
    }

coding problems solutions