# HackerEarth Micro and Array Function problem solution

In this HackerEarth Micro and Array Function problem solution Micro has made a breakthrough. He made a function which he proudly calls Micro's Array Fucntion. It takes an array of integers A and an integer K as input and optimally finds out the number of unordered pairs (i,j),i != j such that A[i] - A[j] >= K.
Micro is getting a lot of recognition because of it. His best friend Mike wants to be a part of it, but for that he needs to make some contribution. He thought of extending Micro's Array function. He wants to make a new function g(A,K) that also takes an array of integers A and an integer K as input and optimally calculates Sigma F(X,K) for all contiguous subarrays X of A. He need your help in this and help here means do the entire task. He'll give you an integer K and an array A having N integers and you need to compute g(A,K).

## HackerEarth Micro and Array Function problem solution.

`#include<bits/stdc++.h>#define ll long longusing namespace std;ll bit[2][300100];inline void init(){    memset(bit, 0, sizeof(bit));}void update(int val, int x, int idx){    while(x <= 3e5){        bit[idx][x] += val;        x += (x&(-x));    }}ll query(int x, int idx){    ll ret = 0;    while(x){        ret += bit[idx][x];        x -= (x&(-x));    }    return ret;}struct node{    int x, i, j;    node(){}    node(int x, int i, int j){        this->x = x;        this->i = i;            this->j = j;    }};bool compare(node a, node b){    return a.x < b.x;}int a[3][300100]={0};int main(){    int t;    ios::sync_with_stdio(false);    cin.tie(0);        cin>>t;    while(t--){        init();        map<ll, int> m;        int n, k; cin>>n>>k;                vector<node> v;        for(int i=1; i<=n; i++){            int temp;cin>>temp;            v.push_back(node(temp, i, 0));            v.push_back(node(temp-k, i, 1));            v.push_back(node(temp+k, i, 2));            }        sort(v.begin(), v.end(), compare);        int cnt = 0;        for(int i=0; i<v.size(); i++){            if(!i or v[i].x != v[i-1].x)cnt++;            a[v[i].j][v[i].i] = cnt;        }           ll ans = 0;        for(int i=1; i<=n; i++){            ll sum = 0;            sum += query(a[1][i], 0);            sum += query(3e5-a[2][i]+1, 1);            update(i, a[0][i], 0);            update(i, 3e5-a[0][i]+1, 1);            ans += (sum*(n-i+1));        }        cout<<ans<<endl;    }    return 0;}`

### Second solution

`#include<bits/stdc++.h>#include<iostream>using namespace std;#define fre     freopen("in.txt","r",stdin);//freopen("0.out","w",stdout)#define abs(x) ((x)>0?(x):-(x))#define MOD 1000000007#define LL signed long long int#define scan(x) scanf("%d",&x)#define print(x) printf("%d\n",x)#define scanll(x) scanf("%lld",&x)#define printll(x) printf("%lld\n",x)#define rep(i,from,to) for(int i=(from);i <= (to); ++i)#define pii pair<int,int>#define MAXN 200000vector<int> G[2*100000+5];int N, K;LL tree[MAXN+5];LL read(LL *bit,int idx){    LL sum = 0;    if(idx==0)        return 0;    while (idx > 0){        sum += bit[idx];        idx -= (idx & -idx);    }    return sum;}void update(LL *bit,int idx ,int val){    while (idx <= MAXN){        bit[idx] += val;        idx += (idx & -idx);    }}map<int,int>mp;LL calc(int *A){    rep(i,1,MAXN)tree[i] = 0;    LL ans = 0;    for(int i=1;i<=N;++i){        ans += read(tree, mp[A[i]-K]) * (N-i+1);        update(tree, mp[A[i]], i);    }    return ans;}int A[100000+5];int main(){    int T;    cin>>T;    while(T--){        vector<int>V;        cin>>N>>K;        rep(i,1,N){            scan(A[i]);            V.push_back(A[i]);            V.push_back(A[i] - K);        }        sort(V.begin(),V.end());        for(int i=0;i<V.size();++i){            mp[V[i]] = i+1;        }        LL ans = 0;        ans = calc(A);        reverse(A+1,A+N+1);        ans = ans + calc(A);        printll(ans);    }}`