# HackerEarth Common Goods problem solution

In this HackerEarth Common Goods problem solution, There are N packets of goods each having some number of items in it. The number of items is in the form of an array A (A[i] items of ith type). There is M number of persons in total each having a share in the goods. They have shares in the form of L and R which means that they hold a share of goods [L....R]. Bob wants Q items. He reports the items one by one.
Each time he takes an item you are required to determine how many people have lost all the items from their share.

## HackerEarth Common Goods problem solution.

`#include<bits/stdc++.h>using namespace std;#define ll intll n,m,q,fir[100005],a[100005],ans[100005];pair<ll,ll>p[100005];ll tree[400005];void buildtree(ll node,ll st,ll en){    if(st==en)    {        tree[node]=fir[st];    }    else    {        ll mid=(st+en)/2;        buildtree(2*node,st,mid);        buildtree(2*node+1,mid+1,en);        tree[node]=max(tree[2*node],tree[2*node+1]);    }}ll query(ll node,ll st,ll en,ll lft,ll rght){    if(rght<st||lft>en)    return 0;    else if(st>=lft&&en<=rght)    return tree[node];    else    {        ll mid=(st+en)/2;        return max(query(2*node,st,mid,lft,rght),query(2*node+1,mid+1,en,lft,rght));    }}int main(){    //ios::sync_with_stdio(0);    ll i,j,k,l,r;    cin>>n;    for(i=1;i<=n;i++)    {        cin>>a[i];    }    cin>>m>>j;    for(i=1;i<=m;i++)    {        cin>>p[i].first>>p[i].second;    }    cin>>q;    for(i=1;i<=q;i++)    {        cin>>j;        if(a[j]>0)        {            a[j]--;            if(a[j]==0)            fir[j]=i;        }    }    for(i=1;i<=n;i++)    {        if(fir[i]==0)        {            fir[i]=INT_MAX;        }    }    buildtree(1,1,n);    for(i=1;i<=m;i++)    {        l=p[i].first;        r=p[i].second;        j=query(1,1,n,l,r);        if(j!=INT_MAX)        {            ans[j]++;        }    }    for(i=1;i<=q;i++)    {        ans[i]+=ans[i-1];    }    for(i=1;i<=q;i++)    cout<<ans[i]<<" ";    return 0;}`

### Second solution

`#include<bits/stdc++.h>#define inf 1000000using namespace std;int n,a[100005],m,lft[100005],rgt[100005],ans[100005],ex[100005],st[400005];int query(int ss,int se,int si,int l,int r){    if(ss>se || se<l || ss>r)return 0;    if(ss>=l && se<=r)return st[si];    int mid=(ss+se)/2;    return max(query(ss,mid,2*si,l,r),query(mid+1,se,2*si+1,l,r));}void build_segment(int ss,int se,int si){    if(ss==se)    {        st[si]=ex[ss];        return;    }    int mid=(ss+se)/2;    build_segment(ss,mid,2*si);    build_segment(mid+1,se,2*si+1);    st[si]=max(st[2*si],st[2*si+1]);}int main(){    cin>>n;    assert(n>=1 && n<=1e5);    for(int i=1;i<=n;i++)    {        cin>>a[i];        assert(a[i]>=1 && a[i]<=1e5);    }    int two;    cin>>m>>two;    assert(m>=1 && m<=1e5);assert(two==2);    for(int i=1;i<=m;i++)    {        cin>>lft[i]>>rgt[i];        assert(lft[i]>=1 && lft[i]<=n);        assert(rgt[i]>=lft[i] && rgt[i]<=n);    }    int q;    cin>>q;    assert(q>=1 && q<=1e5);    for(int i=0;i<=100000;i++)ex[i]=inf;    for(int i=1;i<=q;i++)    {        int temp;        cin>>temp;        assert(temp>=1 && temp<=n);        a[temp]--;        if(a[temp]==0)ex[temp]=i;        //assert(a[temp]>=0);    }    build_segment(1,n,1);    for(int i=1;i<=m;i++)    {        int num=query(1,n,1,lft[i],rgt[i]);        if(num<=q)            ans[num]++;    }    for(int i=1;i<=q;i++)    {        ans[i]+=ans[i-1];        cout<<ans[i]<<" ";    }    return 0;}`