HackerEarth Chemical Reaction problem solution

In this HackerEarth Chemical Reaction problem Ani and his Favourite Chemistry Teacher Lissa were performing an Experiment in the Chemistry Lab. Experiment involves a N step Chemical Reaction. An N step Chemical Reaction requires N different reactants from the periodic table . (Do you know about Periodic Table? No , still you can try solving this problem). N elements are stacked in the bottom up manner with their reacting times. Look at the given figure.

Lissa is very good at performing experiment (offcourse as she is a chemistry teacher). So, she is doing the actual job alone. Ani is there only to provide her a helping hand. After every step, Lissa ordered Ani to put kth element from the stack (counting start from bottom) into the ongoing chemical reaction and record the expected time taken by the chemical reaction to be accomplished.

Expected Time of a Chemical reaction is defined as the maximum of reacting time of all the reactants present in the chemical reaction at that instant of time.

Considering a 6 step Chemical reaction with the same set of reactants given above. Let the order of elements given by Lissa to Ani follows this list.

Note that the list contains N-1 elements only.

HackerEarth Chemical Reaction problem solution.

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<climits>
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define ll long long
#define VI vector<int>
#define PII pair<int,int>
#define VII vector<PII >
#define ft first
#define sd second
#define rz(v,n) v.resize(n)
#define VS vector<string>
#define VL vector<ll>
#define VLL vector<pair<ll,ll> >
#define PLL pair< ll,ll >
#define all(v) v.begin(),v.end()
#define IT iterator
// Input/Output
#define print(v) printf("%d\n",v)
#define printll(v) printf("%lld\n",v)
#define scan(v) scanf("%d",&v)
#define scanll scanf("%lld",&v)
// loops
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
//extra
#define ms(v,val) memset(v,val,sizeof(v))
#define fill(v,val) fill(all(v),val)
#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)
#define PIE 3.14159265358979323846264338327950
#define MOD 1000000007
#ifdef ONLINE_JUDGE
 inline void inp( int &n )
 {
    n=0;
    int ch=getchar_unlocked();int sign=1;
    while( ch < '0' || ch > '9' ){if(ch=='-')sign=-1; ch=getchar_unlocked();}

    while(  ch >= '0' && ch <= '9' )
            n = (n<<3)+(n<<1) + ch-'0', ch=getchar_unlocked();
    n=n*sign;
  }
#else
inline void inp(int &n){
 cin>>n;
}
#endif
#define N 500000
VI st;
void buildst(int idx,int ss,int se){
   if(ss==se){st[idx]=1;return ;}
   int mid=(ss+se)>>1;
   buildst(2*idx+1,ss,mid);
   buildst(2*idx+2,mid+1,se);
   st[idx]=st[2*idx+1]+st[2*idx+2];
}
void update(int idx,int ss,int se,int index){
  if(ss==se){st[idx]=0;return;}
  int mid=(ss+se)>>1;
  if(index<=mid) update(2*idx+1,ss,mid,index);
  else update(2*idx+2,mid+1,se,index);
  st[idx]=st[2*idx+1]+st[2*idx+2];
}
int query(int idx,int ss,int se,int k){
  if(ss==se) return ss;
  int mid=(ss+se)>>1;
  return st[2*idx+1]>=k?query(2*idx+1,ss,mid,k):query(2*idx+2,mid+1,se,k-st[2*idx+1]);
}
char str[N][15];
int main(){

  //#ifdef ONLINE_JUDGE
  // f_in("in1.txt");
   //f_out("out1.txt");
  //#endif
  int t;
  inp(t);
  assert(t<=10);
  while(t--){
   int n;
   inp(n);
   assert(n<=1000000);
   VI arr(n);
   //VS str(n);
   int i;
   FOR(i,0,n) scanf("%s",str[i]);
   FOR(i,0,n) inp(arr[i]);
   int size=(ceil)(log2(n))+1;
   st.resize(1<<size);
   buildst(0,0,n-1);
   int MAX=-1;
   FOR(i,1,n){
    int x;
    inp(x);
    int getx=query(0,0,n-1,x);
    MAX=max(MAX,arr[getx]);
    printf("%s %d\n",str[getx],MAX);
    update(0,0,n-1,getx);
   }
    //x=1;
    int getx=query(0,0,n-1,1);
    MAX=max(MAX,arr[getx]);
    printf("%s %d\n",str[getx],MAX);
    update(0,0,n-1,getx);
  }
  return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;

int A[500005];
char S[500005][11];

int n;

int tree[1000005];
int LIM;

void update(int idx, int val)
{
    while ( idx <= LIM+1 ) {
        tree[idx] += val;
        idx += (idx & (-idx));
    }
    return;
}

int query(int idx)
{
    int res = 0;
    while ( idx > 0 ) {
        res += tree[idx];
        idx -= (idx & (-idx));
    }
    return res;
}

inline void fi(int *a)
{
 register char c=0;
 while (c<33) c=getchar_unlocked();
 *a=0;
 int tmp = 0;
 while (c>33)
 {
     if ( c == 45 ) tmp = 1;
     else *a=*a*10+c-'0';
     c=getchar_unlocked();
 }
 if ( tmp == 1 ) *a = 0-(*a);
}

    
int main()
{
    int t,x,val;
    fi(&t);
    while ( t-- ) {
        fi(&n);
        LIM = (int)log2(n);
        LIM++;
        LIM = 1<<LIM;
        val = -1;
        for ( int i = 1; i <= n; i++ ) scanf("%s", S[i]);
        for ( int i = 1; i <= n; i++ ) fi(&A[i]);
        for ( int i = 0; i <= LIM; i++ ) tree[i] = 0;
        for ( int i = 1; i <= LIM; i++ ) update(i,1);
        for ( int i = 1; i <= n; i++ ) {
            if ( i == n ) x = 1;
            else fi(&x);
            int mask = LIM,L=0,ans;
            while ( mask != 0 && L < n ) {
                int M = (L+mask);
                if ( x == tree[M] ) ans = M;
                else if ( x > tree[M] ) {
                    L = M;
                    x -= tree[M];
                }
                mask >>= 1;
            }
            val = max(val, A[ans]);
            printf("%s %d\n", S[ans], val);
            update(ans,-1);
        }
    }
    return 0;
}