HackerEarth: Chemical Reaction (DS)

HackerEarth: Chemical Reaction (DS)
Idea: This questions asks for implementing basic idea of finding kth odrer 

and deleting that element and again doing same subsequently for large quries.

This can be done easily 

1.) using BIT , where prefix sum is kept by initializing all index to 1.

After that cummulative sum is stored on BIT. so, for finding kth value ,

we need to do Binary search on index, after getting desired index,that value

is made zero by updating -1 value, as +1 value was stored before.

This solution takes execution time: 2.182175

2.) or we also may use segment tree keeping 

prefix sum and quering for kth sum in segment tree node [ this solution 

executes in time: 1.9685

Here, The first solution has been commenting out.

///==================================================///
///                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     500015
#define inf    2000000000
#define MD     3
#define eps    1e-9
///===============================///

/*
int BIT[MX+5];
void add(int p,int v) {
    for(int i=p; i<=MX; i+=i&-i)BIT[i]+=v;
}
int read(int p) {
    int ret=0;
    for(int i=p; i>0; i-=i&-i)ret+=BIT[i];
    return ret;
}
*/

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

void Ins(int id,int l,int r,int p,int v) {
    if(l==r) {
        nd[id]+=v;
        return;
    }
    int md=(l+r)>>1,lft=(id<<1),rgt=lft+1;
    if(p<=md) Ins(lft,l,md,p,v);
    else Ins(rgt,md+1,r,p,v);
    nd[id]=nd[lft]+nd[rgt];
}

int Qry(int id,int l,int r,int k) {
    if(l==r) return l;
    int md=(l+r)>>1,lft=(id<<1),rgt=lft+1;
    int lsm=nd[lft],rsm=nd[rgt];
    if(lsm>=k) return Qry(lft,l,md,k);
    else return Qry(rgt,md+1,r,k-lsm);
}

string s[MX+2];
int main() {
    int tc,m,n,q,i,j,k,x,y,op;
    S(tc);
    while(tc--) {
        S(n);
        fr(i,1,n)cin>>s[i];
        fr(i,1,n)S(ar[i]);
        Build(1,1,n);
        /*
        CLR(BIT);
        fr(i,1,n)add(i,+1);
        */
        int ans=0;
        for(i=1; i<=n; i++) {
            if(i<=n-1)S(x);
            else x=1;
            int ret=Qry(1,1,n,x);
            /*int lo=1,hi=n,ret=n;
              while(lo<=hi) {
                  int md=(lo+hi)>>1;
                  if( read(md)>=x ) {
                      ret=min(ret,md);
                      hi=md-1;
                  } else lo=md+1;
              }
            */
            Ins(1,1,n,ret,-1);
            ans=max(ans,ar[ret]);
            printf("%s %d\n",s[ret].c_str(),ans);
        }
    }
    return 0;
}