10084 | 2024. 03. 26 17:23:18 | matyi | Bináris fa magassága (50 pont) | cpp17 | Elfogadva 50/50 | 133ms | 5744 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;
}
}
void alakit(int suly[], int hossz[], int csp , int darabcsucs)
{
hossz[csp]=max(hossz[csp*2]+suly[csp*2] , hossz[csp*2+1]+suly[csp*2+1]);
if (csp/2!=0)
{
alakit(suly,hossz,csp/2, darabcsucs);
}
}
int main()
{
int n,m;
//ifstream fin("be.in");
cin>>n>>m;
int darabcsucs=gyorshatvany(n);
int suly[darabcsucs]={0},hossz[darabcsucs]={0};
int x,y;
for (int i=2;i<darabcsucs;i++)
{
suly[i]=1;
}
for (int i=darabcsucs/2-1;i>=1;i--)
{
hossz[i]=hossz[i*2]+1;
}
for (int i=1;i<=m;i++)
{
cin>>x>>y;
suly[x]=y;
alakit(suly,hossz,x/2,darabcsucs);
cout<<hossz[1]<< endl;
}
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 50/50 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1876 KiB | |||
2 | Elfogadva | 0/0 | 85ms | 3140 KiB | |||
3 | Elfogadva | 2/2 | 4ms | 2424 KiB | |||
4 | Elfogadva | 2/2 | 4ms | 2484 KiB | |||
5 | Elfogadva | 2/2 | 4ms | 2748 KiB | |||
6 | Elfogadva | 2/2 | 4ms | 2768 KiB | |||
7 | Elfogadva | 3/3 | 4ms | 2896 KiB | |||
8 | Elfogadva | 3/3 | 4ms | 3040 KiB | |||
9 | Elfogadva | 3/3 | 4ms | 3132 KiB | |||
10 | Elfogadva | 3/3 | 4ms | 3256 KiB | |||
11 | Elfogadva | 2/2 | 100ms | 4532 KiB | |||
12 | Elfogadva | 2/2 | 128ms | 4732 KiB | |||
13 | Elfogadva | 2/2 | 100ms | 4788 KiB | |||
14 | Elfogadva | 2/2 | 133ms | 5036 KiB | |||
15 | Elfogadva | 2/2 | 85ms | 5120 KiB | |||
16 | Elfogadva | 2/2 | 79ms | 5204 KiB | |||
17 | Elfogadva | 2/2 | 79ms | 5332 KiB | |||
18 | Elfogadva | 2/2 | 123ms | 5416 KiB | |||
19 | Elfogadva | 2/2 | 82ms | 5692 KiB | |||
20 | Elfogadva | 3/3 | 82ms | 5720 KiB | |||
21 | Elfogadva | 3/3 | 86ms | 5736 KiB | |||
22 | Elfogadva | 3/3 | 96ms | 5736 KiB | |||
23 | Elfogadva | 3/3 | 81ms | 5744 KiB |