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


HackerEarth Micro and Array Function problem solution.

#include<bits/stdc++.h>
#define ll long long
using 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 200000
vector<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);
}
}