83622024-01-15 00:13:56zoliBináris fa magassága (50 pont)cpp17Időlimit túllépés 20/50600ms4188 KiB
#include <iostream>

using namespace std;
int a[65536]; ///2^16;
int os[65536];
int N,M;
int cs[50001],h[50001]; ///csucsok, hosszak
int mhat,maxh=0;
void frissit(int cs, int valt)
{
    a[cs]+=valt;
    if(2*cs<mhat)
    {   frissit(2*cs,valt); frissit(2*cs+1,valt); }
}
int maxmag()
{
    int k=mhat/2;
    int maxi=a[k];
    for(int i=k+1;i<mhat;i++) if(a[i]>maxi)maxi=a[i];
    return maxi;
}
void kiir()
{
    for(int i=1;i<mhat;i++) cout<<a[i]<<" ";
    cout<<endl;
}
int szint(int x)
{
    int db=0;
    while(x>1)
    {
        db++;x/=2;
    }
    return db;
}
void keres(int x, int & k, int & v) ///kezdoertek a levelek szintjen
{
    v=x+1;
    while(x<mhat/2)
    {
        x*=2;v=v*2;
    }
    k=x;
    v--;
}
void frissit2(int k, int v, int valt, int &maxi)
{
    for(int i=k;i<=v;i++)
    {
        a[i]+=valt;
        //maxi=max(a[i],maxi);
    }

}
void be()
{
    ///inicializal a
    cin>>N>>M;
    mhat=(1<<N);
    a[1]=0;os[1]=0;
    for(int i=2;i<mhat;i++)
       {
         a[i]=a[i/2]+1;os[i]=1;
       }
    //kiir();
    for(int i=1;i<=M;i++)
    {
        cin>>cs[i]>>h[i];
    }
    for(int i=1;i<=M;i++)
    {
        int valtozas=h[i]-os[cs[i]];
        os[cs[i]]=h[i];
        int k,v;
        keres(cs[i],k,v);
        //frissit(cs[i],valtozas);
        maxh=0;
        frissit2(k,v,valtozas,maxh);
        cout<<maxmag()<<"\n";
        //cout<<maxh<<"\n";
      //  kiir();cout<<k<<v<<valtozas;
    }
}

int main()
{
    be();

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
base20/50
1Elfogadva0/03ms1892 KiB
2Időlimit túllépés0/0541ms2112 KiB
3Elfogadva2/23ms2300 KiB
4Elfogadva2/23ms2516 KiB
5Elfogadva2/23ms2600 KiB
6Elfogadva2/23ms2728 KiB
7Elfogadva3/34ms3216 KiB
8Elfogadva3/33ms3312 KiB
9Elfogadva3/33ms3284 KiB
10Elfogadva3/33ms3452 KiB
11Időlimit túllépés0/2600ms3708 KiB
12Időlimit túllépés0/2574ms3748 KiB
13Időlimit túllépés0/2558ms3680 KiB
14Időlimit túllépés0/2550ms3684 KiB
15Időlimit túllépés0/2580ms3932 KiB
16Időlimit túllépés0/2556ms3852 KiB
17Időlimit túllépés0/2574ms3880 KiB
18Időlimit túllépés0/2565ms3960 KiB
19Időlimit túllépés0/2578ms4040 KiB
20Időlimit túllépés0/3565ms4092 KiB
21Időlimit túllépés0/3564ms4008 KiB
22Időlimit túllépés0/3569ms4036 KiB
23Időlimit túllépés0/3546ms4188 KiB