Submission #494363

#	Time	Username	Problem	Language	Result	Execution time	Memory
494363		stefantaga	Growing Trees (BOI11_grow)	C++14	100 / 100	145 ms	5064 KiB

grow

#include <bits/stdc++.h>

using namespace std;
const int NMAX = 100005;
int n;
struct Arb{
    int arb[4*NMAX],lazy[4*NMAX];
    void propaga(int st,int dr,int nod)
    {
        if (st==dr)
        {
            return;
        }
        if (lazy[nod]==0)
        {
            return;
        }
        lazy[2*nod]+=lazy[nod];
        lazy[2*nod+1]+=lazy[nod];
        arb[2*nod]+=lazy[nod];
        arb[2*nod+1]+=lazy[nod];
        lazy[nod]=0;
        return;
    }
    void update(int st,int dr,int nod,int ua,int ub,int val)
    {
        if (st>ub||ua>dr)
        {
            return;
        }
        propaga(st,dr,nod);
        if (ua<=st&&dr<=ub)
        {
            arb[nod]+=val;
            lazy[nod]+=val;
            return;
        }
        int mij=(st+dr)/2;
        update(st,mij,2*nod,ua,ub,val);
        update(mij+1,dr,2*nod+1,ua,ub,val);
        arb[nod]=max(arb[2*nod],arb[2*nod+1]);
    }
    int query(int st,int dr,int nod,int poz)
    {
        propaga(st,dr,nod);
        if (st==dr)
        {
            return arb[nod];
        }
        int mij=(st+dr)/2;
        if (poz<=mij)
        {
            return query(st,mij,2*nod,poz);
        }
        return query(mij+1,dr,2*nod+1,poz);
    }
    int parcurge(int st,int dr,int nod,int k) /// vreau cea mai mare pozitie poz pentru care v[poz]<=k
    {
        propaga(st,dr,nod);
        if (st==dr)
        {
            if (arb[nod]>=k)
            {
                return st;
            }
            return n+1;
        }
        int mij=(st+dr)/2;
        if (arb[2*nod]<k)
        {
            return parcurge(mij+1,dr,2*nod+1,k);
        }
        return min(parcurge(st,mij,2*nod,k),mij+1);
    }
}Arb1;
int q,i,v[NMAX],poz1,poz2,poz3,valoare,salut;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>n>>q;
    for (i=1;i<=n;i++)
    {
        cin>>v[i];
    }
    sort (v+1,v+n+1);
    for (i=1;i<=n;i++)
    {
        Arb1.update(1,n,1,i,i,v[i]);
    }
    for (i=1;i<=q;i++)
    {
        char tip;
        cin>>tip;
        if (tip=='F')
        {
            int c,h;
            cin>>c>>h;
            poz1=Arb1.parcurge(1,n,1,h);
            if (poz1==n+1)
            {
                continue;
            }
            if (n-poz1+1<=c)
            {
                Arb1.update(1,n,1,poz1,n,1);
            }
            else
            {
                /// am de la poz1 la poz1+c-1 trebuie sa updatez.
                valoare = Arb1.query(1,n,1,poz1+c-1);
                poz2 = Arb1.parcurge(1,n,1,valoare);
                poz3 = Arb1.parcurge(1,n,1,valoare+1)-1;
                if (poz1<=poz2-1)
                {
                    Arb1.update(1,n,1,poz1,poz2-1,1);
                }
                int cataramas=c-(poz2-poz1);
                Arb1.update(1,n,1,poz3-cataramas+1,poz3,1);
            }
        }
        else
        {
            int st,dr;
            cin>>st>>dr;
            poz1=Arb1.parcurge(1,n,1,st);
            poz2=Arb1.parcurge(1,n,1,dr+1);
            cout<<poz2-poz1<<'\n';
        }
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10