97442024-03-05 18:18:35matyiBináris fa magassága (50 pont)cpp17Time limit exceeded 32/50583ms5372 KiB
#include <iostream>
#include <fstream>

using namespace std;

int gyorshatvany(int n)
{
    if (n==0)
        return 1;
    else
    {
        int hatvany=gyorshatvany(n/2); // 2^n/2
        if (n%2==0)
        {
            return hatvany * hatvany;
        }
        else
            return hatvany * hatvany * 2;
    }
}

int main()
{

    int n,m;
    //ifstream fin("be.in");
    cin>>n>>m;
    int darabcsucs=gyorshatvany(n);
    int o=darabcsucs/2;
    int suly[darabcsucs]={0},hossz[o]={0}, szint[darabcsucs]={0};
    int x,y;
    szint[1]=1;
    for (int i=2;i<darabcsucs;i++)
    {
        suly[i]=1;
        szint[i]=szint[i/2]+1;
    }
    for (int i=0;i<o;i++)
    {
        hossz[i]=n-1;
    }
    int globalmaxi=-1, globalhely;
    for (int i=1;i<=m;i++)
    {
        cin>>x>>y;
        int kulonbseg=y-suly[x];
        suly[x]=y;
        int hatvany=gyorshatvany(n-szint[x]);
        int kezd=hatvany*x-(o);
        int veg=kezd+hatvany-1;
        int maxi=-1, hely;
        for (int i=kezd;i<=veg;i++)
        {
            hossz[i]+=kulonbseg;
            if (hossz[i]>maxi){
                maxi=hossz[i];
                hely=i;
            }
        }
        if (maxi >= globalmaxi)
        {
            globalmaxi = maxi;
            globalhely = hely;
        }
        else
        {
            if (globalhely>=kezd and globalhely<=veg)
            {
                globalmaxi=maxi;
                for (int i=0;i<kezd;i++)
                {
                    if (hossz[i]>globalmaxi)
                    {
                        globalmaxi=hossz[i];
                        globalhely=i;
                    }

                }
                for (int i=veg+1;i<o;i++)
                {
                    if (hossz[i]>globalmaxi)
                    {
                        globalmaxi=hossz[i];
                        globalhely=i;
                    }

                }
            }
        }
        cout<<globalmaxi<< endl;
    }
    return 0;
}
SubtaskSumTestVerdictTimeMemory
base32/50
1Accepted0/03ms1744 KiB
2Accepted0/0363ms3268 KiB
3Accepted2/24ms2236 KiB
4Accepted2/24ms2356 KiB
5Accepted2/24ms2660 KiB
6Accepted2/24ms2560 KiB
7Accepted3/34ms2752 KiB
8Accepted3/34ms2988 KiB
9Accepted3/34ms3100 KiB
10Accepted3/34ms3340 KiB
11Accepted2/2286ms4704 KiB
12Accepted2/2485ms4800 KiB
13Time limit exceeded0/2583ms3472 KiB
14Time limit exceeded0/2577ms3520 KiB
15Time limit exceeded0/2580ms3616 KiB
16Accepted2/2347ms5124 KiB
17Accepted2/2344ms5036 KiB
18Accepted2/2347ms5160 KiB
19Accepted2/2349ms5372 KiB
20Time limit exceeded0/3569ms4324 KiB
21Time limit exceeded0/3569ms4420 KiB
22Time limit exceeded0/3578ms4492 KiB
23Time limit exceeded0/3569ms4544 KiB