oj.uz

Submission #494363

# Submission time Handle Problem Language Result Execution time Memory
494363 2021-12-15T10:27:22 Z stefantaga Growing Trees (BOI11_grow) C++14
100 / 100
 145 ms 5064 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 4024 KB Output is correct
2 Correct 103 ms 4424 KB Output is correct
3 Correct 47 ms 4372 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 4 ms 456 KB Output is correct
4 Correct 2 ms 336 KB Output is correct
5 Correct 42 ms 1524 KB Output is correct
6 Correct 54 ms 1652 KB Output is correct
7 Correct 5 ms 464 KB Output is correct
8 Correct 24 ms 1232 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 1732 KB Output is correct
2 Correct 51 ms 1836 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 33 ms 1372 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 1992 KB Output is correct
2 Correct 47 ms 1724 KB Output is correct
3 Correct 9 ms 592 KB Output is correct
4 Correct 50 ms 1832 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 2840 KB Output is correct
2 Correct 96 ms 4040 KB Output is correct
3 Correct 16 ms 1232 KB Output is correct
4 Correct 56 ms 4044 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 3796 KB Output is correct
2 Correct 101 ms 4040 KB Output is correct
3 Correct 45 ms 4304 KB Output is correct
4 Correct 14 ms 1304 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 3788 KB Output is correct
2 Correct 76 ms 4028 KB Output is correct
3 Correct 50 ms 4384 KB Output is correct
4 Correct 15 ms 1300 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 4472 KB Output is correct
2 Correct 96 ms 3948 KB Output is correct
3 Correct 51 ms 3348 KB Output is correct
4 Correct 68 ms 3880 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 4152 KB Output is correct
2 Correct 101 ms 4396 KB Output is correct
3 Correct 145 ms 4528 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 5064 KB Output is correct