HackerEarth Shil and Special Pairs problem solution

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.

#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;
}

coding problems solutions