HackerEarth Heights of students problem solution

In this HackerEarth Heights of students problem solution, All N students of a class are standing in a straight line behind one other student. For example, student 2 is standing behind student 1, student 3 is standing behind student 2, and so on until the Nth student.

The happiness level of a student is determined by the number of students standing before him whose height is strictly greater than him. The total happiness of the class is the sum of the happiness level of all students.

Now you can help minimize this sadness. Your task is to minimize the happiness level of the class.

Note: You can select one student from anywhere in the line and place him at the end of the line.

HackerEarth Heights of students problem solution.

#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define mp make_pair
#define pb push_back
#define ll long long int
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};

int bit1[100005] , bit2[100005];
int n;

void update1(int idx,int val){
    while(idx<=n){
        bit1[idx]+=val;
        idx+= (idx&(-idx));
    }
}

int getsum1(int idx){
    int sum=0;
    while(idx>0){
        sum+=bit1[idx];
        idx-= (idx&(-idx));
    }
    return sum;
}

void update2(int idx,int val){
    while(idx<=n){
        bit2[idx]+=val;
        idx+= (idx&(-idx));
    }
}

int getsum2(int idx){
    int sum=0;
    while(idx>0){
        sum+=bit2[idx];
        idx-= (idx&(-idx));
    }
    return sum;
}

int main()
{
    int i,j,x,y,t;
    cin>>t;
    assert(0<t && t<=5);
    while(t--){
        
        cin>>n;
        assert(0<n && n<=100000);
        memset(bit1,0,sizeof(bit1));
        memset(bit2,0,sizeof(bit2));
        ll a[n+5],b[n+5];
        map <ll,int> m;
        for(i=1;i<=n;++i){
            cin>>a[i];
            assert(0<a[i] && a[i]<=10000000000);
            b[i]=a[i];
        }
        sort(b+1,b+n+1);
        b[0]=0;
        int val = 0;
        for(i=1;i<=n;++i){
            if(b[i]>b[i-1]){
                ++val;
                m[b[i]]=val;
            }
        }
        for(i=1;i<=n;++i){
            a[i]= m[a[i]];
            //cout<<a[i]<<" ";
        }
        ll ans =0;
        //cout<<getsum1(n+2);
        for(i=1;i<=n;++i){
        //  cout<<(ll)getsum1(n)-(ll)getsum1(a[i])<<"n";
            b[i] = (ll)getsum1(n)-(ll)getsum1(a[i]) ;
             ans += b[i];
             update1(a[i],1);
        }
        //cout<<ans<<"n";
        ll ans2 = ans;
        for(i=n;i>0;--i){
            ll add = (ll)getsum1(n)-(ll)getsum1(a[i]) ;
            ll sub = (ll)getsum2(a[i]-1) + b[i];
        //  cout<<i<<" "<<sub<<" "<<add<<"n";
            ans2 = min(ans2,ans+add-sub);
            update2(a[i],1);
        }
        cout<<ans2<<"n";
    }   
    
return 0;
}

Second solution

#include<bits/stdc++.h>
#define ll long long
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define vll vector<ll>
#define fulll(v) v.begin(),v.end()
#define vecin(n, v) for(ll i=0; i<n;i++) cin>>v[i];
#define rep(i, s, n) for(ll i=(ll)s;i<(ll)n;i++)
#define rrep(i, s, n) for(ll i=(ll)s;i>=(ll)n;i--)
#define pb push_back
#define endl "n"
#define MAX 100005

using namespace std;

vll st[4*MAX];
ll arr[MAX];
ll n;

vll merge(vll a, vll b){
     vll ans;
     auto it1=a.begin(), it2=b.begin();
     while(it1!=a.end() && it2!=b.end()){
         if(*it1<*it2)
             ans.pb(*it1), it1++;
         else
             ans.pb(*it2), it2++;
     }
     for(;it1!=a.end();it1++)
             ans.pb(*it1);
     for(;it2!=b.end();it2++)
             ans.pb(*it2);
     return ans;
}
vll build(ll node, ll sl, ll sr){
     if(sl==sr)
         st[node].pb(arr[sl]);
     else
         st[node]=merge(build(2*node+1, sl, (sl+sr)/2), build(2*node+2, 
(sl+sr)/2+1, sr));
     return st[node];
}

ll query1(ll node, ll sl, ll sr, ll ql, ll qr, ll k){
     if(ql>qr)
         swap(ql, qr);
     if(ql<=sl && sr<=qr)
         return (upper_bound(fulll(st[node]), k)-st[node].begin());
     if(qr<sl||sr<ql)
         return 0;
     ll f=query1(2*node+1, sl, (sl+sr)/2, ql, qr, k) + query1(2*node+2, 
(sl+sr)/2+1, sr, ql, qr, k);
     return f;
}

ll query2(ll node, ll sl, ll sr, ll ql, ll qr, ll k){
     if(ql>qr)
         swap(ql, qr);
     if(ql<=sl && sr<=qr)
         return lower_bound(fulll(st[node]), k)-st[node].begin();
     if(qr<sl||sr<ql)
         return 0;
     ll f=query2(2*node+1, sl, (sl+sr)/2, ql, qr, k) + query2(2*node+2, 
(sl+sr)/2+1, sr, ql, qr, k);
     return f;
}

int main(){
    fast
    ll t;
    cin>>t;
    while(t--){
        memset(st, 0, sizeof(st));
        memset(arr, 0, sizeof(arr));
        cin>>n;
        vll v(n), w(n);
        vecin(n,arr);
        build(0,0,n-1);
        rep(i,0,n)
            w[i]=query2(0, 0, n-1, i, n-1, arr[i]);
        rep(i,0,n)
            v[i]=n-query1(0, 0, n-1, 0, n-1, arr[i]);
        ll mx=0, s=0, mn=LONG_MAX;
        rep(i,0,n)
            s+=w[i];
        rep(i,0,n){
            mn = min(mn, s-w[i]+v[i]);
        }
        cout<<mn<<endl;
    }
    return 0;
}