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 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("%dn",x)
#define scanll(x) scanf("%lld",&x)
#define printll(x) printf("%lldn",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);
    }
}

HackerEarth Micro and Array Function problem solution.

Second solution

Leave a Reply