118762024-11-13 18:57:0042Bináris fa magassága (50 pont)python3Time limit exceeded 40/50600ms5004 KiB
# O(2^N+M*N)
from sys import stdin, stdout
input=stdin.readline

N,M=[int(x) for x in input().split()]
cur=[-1,N-1]
for i in range(N-1):cur+=[N-2-i]*2**(i+1)
elh=[-1]+[1]*(2**N-1)
for i in range(M):
 a,b=[int(x) for x in input().split()]
 elh[a]=b
 while a>1:
  a//=2
  cur[a]=max(cur[2*a]+elh[2*a],cur[2*a+1]+elh[2*a+1])
 print(cur[1])
SubtaskSumTestVerdictTimeMemory
base40/50
1Accepted0/016ms3128 KiB
2Accepted0/0384ms4896 KiB
3Accepted2/217ms3128 KiB
4Accepted2/218ms3216 KiB
5Accepted2/219ms3116 KiB
6Accepted2/218ms3220 KiB
7Accepted3/319ms3128 KiB
8Accepted3/319ms3320 KiB
9Accepted3/319ms3304 KiB
10Accepted3/320ms3232 KiB
11Time limit exceeded0/2583ms4904 KiB
12Time limit exceeded0/2598ms5004 KiB
13Time limit exceeded0/2600ms4896 KiB
14Time limit exceeded0/2587ms4852 KiB
15Time limit exceeded0/2574ms4832 KiB
16Accepted2/2404ms4896 KiB
17Accepted2/2381ms4896 KiB
18Accepted2/2416ms4896 KiB
19Accepted2/2372ms4896 KiB
20Accepted3/3437ms4908 KiB
21Accepted3/3441ms4896 KiB
22Accepted3/3425ms4896 KiB
23Accepted3/3435ms4992 KiB