HackerEarth: Little Deepu and Array (Segment tree)

HackerEarth: Little Deepu and Array (Segment tree)
///==================================================///
///                HELLO WORLD !!                    ///
///                  IT'S ME                         ///
///               BISHAL GAUTAM                      ///
///         [ bsal.gautam16@gmail.com ]              ///
///==================================================///
#include<bits/stdc++.h>
#define X first
#define Y second
#define mpp make_pair
#define nl printf("\n")
#define SZ(x) (int)(x.size())
#define pb(x) push_back(x)
#define pii pair<int,int>
#define pll pair<ll,ll>
///---------------------
#define S(a) scanf("%d",&a)
#define P(a) printf("%d",a)
#define SL(a) scanf("%lld",&a)
#define S2(a,b) scanf("%d%d",&a,&b)
#define SL2(a,b) scanf("%lld%lld",&a,&b)
///------------------------------------
#define all(v) v.begin(),v.end()
#define CLR(a) memset(a,0,sizeof(a))
#define SET(a) memset(a,-1,sizeof(a))
#define fr(i,a,n) for(int i=a;i<=n;i++)
using namespace std;
typedef long long ll;
///==========CONSTANTS=============///
///  Digit     0123456789012345678 ///
#define MX     100004
#define inf    1000000010
#define MD     1000000007LL
#define eps    1e-9
///===============================///

int ar[MX+2],nd[(4*MX)+2],mk[4*MX+2];

void Build(int id,int l,int r) {
    if(l==r) {
        nd[id]=ar[l];
        return;
    }
    int md=(l+r)>>1,lft=(id<<1),rgt=lft+1;
    Build(lft,l,md);
    Build(rgt,md+1,r);
    nd[id]=min(nd[lft],nd[rgt]);
}

void Upd(int id,int l,int r,int q1,int q2,int v) {
    if( l==q1 && r==q2 ) {
        nd[ id ]+=v;
        mk[ id ]+=v;
        return;
    }
    int md=(l+r)>>1,lft=(id<<1),rgt=lft+1;
    if( mk[id]!=0 ) {
        int vv=mk[id];
        nd[lft]+=vv;
        nd[rgt]+=vv;
        mk[lft]+=vv;
        mk[rgt]+=vv;
        mk[id]=0;
    }
    if( q2<=md ) Upd(lft,l,md,q1,q2,v);
    else if(q1>md) Upd(rgt,md+1,r,q1,q2,v);
    else {
        Upd(lft,l,md,q1,md,v);
        Upd(rgt,md+1,r,md+1,q2,v);
    }
    nd[id]=min(nd[lft],nd[rgt]);
}

int Qry(int id,int l,int r,int q1,int q2) {
    if(l==q1 && r==q2) return nd[id];
    int md=(l+r)>>1,lft=(id<<1),rgt=lft+1;
    if( mk[id]!=0 ) {
        int vv=mk[id];
        nd[lft]+=vv;
        nd[rgt]+=vv;
        mk[lft]+=vv;
        mk[rgt]+=vv;
        mk[id]=0;
    }
    nd[id]=min(nd[lft],nd[rgt]);
    if( q2<=md ) return Qry(lft,l,md,q1,q2);
    else if(q1>md) return Qry(rgt,md+1,r,q1,q2);
    else {
        int x=Qry(lft,l,md,q1,md);
        int y=Qry(rgt,md+1,r,md+1,q2);
        return min(x,y);
    }
}

int p[MX+2];
bool cmp(int i,int j) {
    return ar[i]<ar[j];
}
int ans[MX+2];
int main() {
    int n,m,i,j,k,x;
    S(n);
    fr(i,1,n)S(ar[i]);
    fr(i,1,n)p[i]=i;
    sort( p+1,p+n+1,cmp );///Sorting index based on lower val;
    sort( ar+1,ar+n+1 );
    Build(1,1,n);
    S(m);
    while(m--) {
        S(x);
        int lo=1,hi=n,ret=-1;
        while(lo<=hi) {
            int md=(lo+hi)>>1; ///Length;
            int idx=(n-md+1);
            int qr=Qry(1,1,n,idx,n);
            if( qr>x ) {
                ret=idx;
                lo=md+1;
            } else hi=md-1;
        }
        if(ret!=-1) {
            Upd(1,1,n,ret,n,-1);
        }
    }
    fr(i,1,n) {
        ans[ p[i] ]=Qry(1,1,n,i,i);
    }
    printf("%d",ans[1]);
    fr(i,2,n) {
        printf(" %d",ans[i]);
    }
    nl;
    return 0;
}