In this HackerEarth Shil and Special Pairs problem solution Shil has a permutation p1 , p2 .. pN of numbers from 1 to N and M queries. Each query consists of two integers l and r . Answer to each query is total number of pairs[i , j] such that l ≤ i ≤ j ≤ r and|pi - pj| ≤ D.


HackerEarth Shil and Special Pairs problem solution


HackerEarth Shil and Special Pairs problem solution.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define f first
#define s second
#define mod 1000000007
#define inf 1e8

#define pi pair<ll,ll>
#define pii pair<pi,ll>
#define f first
#define mp make_pair
#define pb push_back
#define s second
#define rep(i,n) for(int i=0;i<n;i++)
#define forup(i,a,b) for(int i=a;i<=b;i++)
ll bt[100011];
int N;
void update(int ind){
while(ind<=N){
bt[ind]++;
ind+=(ind&-ind);
}
}
ll query(int ind){
ll ans=0;
while(ind>0){
ans+=bt[ind];
ind-=(ind&-ind);
}
return ans;
}
bool func(pii a,pii b){
return a.f.s<b.f.s;
}
int pos[100011];
ll ans[100011];
int main(){
freopen("output-10.txt","w",stdout);
freopen("input-10.txt","r",stdin);
int M,D;
cin >> N >> M >> D;
int p[N+1];
for(int i=1;i<=N;i++){
cin >> p[i];
pos[p[i]]=i;
}
vector<pii>Q;
int l,r,ind;
rep(i,M){
cin >> l >> r;
Q.push_back( mp( mp(l,r),i ) );
}
sort(Q.begin(),Q.end(),func);
int j=0;
for(int i=1;i<=N;i++){

for(int k=max(1,p[i]-D);k<=min(N,p[i]+D);k++){
if(pos[k]<=i){
update(pos[k]);
}
}

while(j<Q.size() and Q[j].f.s==i){
ans[Q[j].s]=query(Q[j].f.s)-query(Q[j].f.f-1);
j++;
}

}
rep(i,M){
cout<<ans[i]<<"\n";
}
}

Second solution

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long int
#define pb push_back
#define mk make_pair
#define maxi 100002
#define pp pair<pair<ll,ll>,ll>
ll power(ll a, ll b) {
ll x = 1, y = a;
while(b > 0) {
if(b%2 == 1) {
x=(x*y);
if(x>mod) x%=mod;
}
y = (y*y);
if(y>mod) y%=mod;
b /= 2;
}
return x;
}
ll tree[100002];
ll read(ll idx)
{
ll sum = 0;
while (idx > 0){
sum += tree[idx];
idx -= (idx & -idx);
}
return sum;
}
void update(ll idx ,ll val)
{
while (idx <= maxi) {
tree[idx] += val;
idx += (idx & -idx);
}
}
bool cmp(pp x, pp y)
{
if(x.first.second >= y.first.second) {
return false;
}
return true;
}
int main()
{
ll n,m,d,c,i,j,k,id,p,q;
cin>>n>>m>>d;
k = 0;
ll a[n+2],idx[n+2],ans[m+2],check[n+2][2];
for(i = 1; i <= n; i++) {
cin>>a[i];
idx[a[i]] = i;
check[i][0] = min(n,a[i]+d);
check[i][1] = max(1LL,a[i]-d);
}
ll l,r;
vector<pp>dat;
for(i = 1; i <= m; i++) {
cin>>l>>r;
dat.push_back(make_pair(make_pair(l,r),i));
}
sort(dat.begin(),dat.end(),cmp);
for(i = 1; i <= n; i++) {
for(j = check[i][1]; j <= check[i][0]; j++) {
update(idx[j],idx[j] <= i);
}
for(; k < n && dat[k].first.second == i; k++) {
p = dat[k].first.first;
q = dat[k].first.second;
if(p > 1) {
ans[dat[k].second] = read(q)-read(p-1);
}
else {
ans[dat[k].second] = read(q);
}
}
}
for(i = 1; i <= m; i++) {
cout<<ans[i]<<endl;
}
return 0;
}