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


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.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();
}
}