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 A : push element A in the stack.
- 0 : pop one element from stack.
- 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.
#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;
}