HackerEarth Convoluted Operations problem solution

by
In this HackerEarth Convoluted Operations problem solution, Mishki is quite interested in playing games, and recently she found an empty stack. Now she wants to perform 3 types of operations on the stack:
  1. 1 A : push element A in the stack.
  2. 0 : pop one element from stack.
  3. 2 K X : find how many elements were less than X present in the stack, after performing Kth operation on the stack.
Can you help her in performing the above operations ?
HackerEarth Convoluted Operations problem solution

HackerEarth Convoluted Operations problem solution.

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int ma = 5e5+5;

ll n, ans[ma], pus[ma], bit[ma],op[ma], val[ma], compr[ma];
pair <ll, ll> p[ma];
vector < pair<ll,ll> >  v[ma];

void update(int x, int val)
{
  
  while(x<=5e5)
  {
    bit[x]+=val;
    x = x + (x&-x);
  }
}
int query(int x)
{

  int an=0;
  while(x>0)
  {
    an+=bit[x];
    x = x&(x-1);
  }
  return an;
}
int main(int argc, char* argv[])
{
  //freopen(argv[1],"r",stdin);
  //freopen(argv[2],"w",stdout);*/
  cin>>n;
  ll x,y,k,q=0,opr=1,cnt=0;

  for(int i=1;i<=n;i++)
  {
    cin>>x;
    if(x==1)
    {
      cin>>y;
      p[i] = make_pair(x,y);
      compr[cnt++] = y;
    }
    else if(x==0)
      p[i] = make_pair(x,-1);
    else
    {
      p[i] = make_pair(-1,-1);
      cin>>op[q]>>val[q];
      compr[cnt++] = val[q];
      q++;
    }
  }
  //compression
  sort(compr, compr+cnt);
  for(int i=1;i<=n;i++)
  {
    
    if(p[i].first!=-1 and p[i].second!=-1)
    {
      p[i].second = lower_bound(compr, compr+cnt, p[i].second) - compr+1;
    }

  }
  for(int i=0;i<q;i++)
  {
    val[i] = lower_bound(compr, compr+cnt, val[i]) - compr+1;
  }

  for(int i=0;i<q;i++)
  {
    v[op[i]].push_back(make_pair(val[i],i));
  }
  int o=0;
  for(int i=1;i<=n;i++)
  {
      if(p[i].first==1)
      {
        update(p[i].second,1); 
        pus[o++] = i;
      }
      else if(p[i].first==0)
      {
        update(p[pus[o-1]].second,-1);
        o--;
      }

      if(v[i].size())
      {
        for(int j=0;j<v[i].size();j++)
        {
          ans[v[i][j].second] = query(v[i][j].first-1);
        }
      }
  }
  for(int i=0;i<q;i++)
  {
    cout<<ans[i]<<endl;
  }
  return 0;
}

Second solution

#include <bits/stdc++.h>

using namespace std;

int N;
int A[500001];
vector<int> adj[500001];
vector<int> q[500001];
int T[500001];
int P[500001];
int X[500001];
int C[500001], NC;
int bit[500001];
int ans[500001];

void add(int x, int v)
{
    for(x=lower_bound(C, C+NC, x)-C+1; x<=NC; x+=x&-x)
        bit[x]+=v;
}

int sum(int x)
{
    int ret=0;
    for(x=lower_bound(C, C+NC, x)-C+1; x>0; x-=x&-x)
        ret+=bit[x];
    return ret;
}

void dfs(int u)
{
    for(auto& it: q[u])
        ans[it]=sum(X[it]);
    for(auto& v: adj[u])
    {
        add(A[v]+1, 1);
        dfs(v);
        add(A[v]+1, -1);
    }
}

int main()
{
    memset(ans, -1, sizeof ans);
    scanf("%d", &N);
    assert(1<=N && N<=500000);
    int n=1;
    for(int i=1; i<=N; i++)
    {
        int op;
        scanf("%d", &op);
        assert(0<=op && op<=2);
        if(op==0)
        {
            assert(T[i-1]);
            T[i]=P[T[i-1]];
        }
        else if(op==1)
        {
            scanf("%d", A+n);
            assert(0<=A[n] && A[n]<=1000000000);
            C[NC++]=A[n]+1;
            P[n]=T[i-1];
            adj[P[n]].push_back(n);
            T[i]=n++;
        }
        else
        {
            int k, x;
            scanf("%d%d", &k, &x);
            assert(1<=k && k<=i);
            assert(0<=x && x<=1000000000);
            C[NC++]=x;
            X[i]=x;
            T[i]=T[i-1];
            q[T[k]].push_back(i);
        }
    }
    sort(C, C+NC);
    dfs(0);
    for(int i=1; i<=N; i++) if(ans[i]!=-1)
        printf("%dn", ans[i]);
    return 0;
}