118772024-11-13 18:57:2942Bináris fa magassága (50 pont)pypy3Elfogadva 50/50119ms25228 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])
RészfeladatÖsszpontTesztVerdiktIdőMemória
base50/50
1Elfogadva0/043ms19476 KiB
2Elfogadva0/0100ms25012 KiB
3Elfogadva2/259ms21392 KiB
4Elfogadva2/271ms21744 KiB
5Elfogadva2/286ms21840 KiB
6Elfogadva2/274ms22476 KiB
7Elfogadva3/371ms22232 KiB
8Elfogadva3/371ms22208 KiB
9Elfogadva3/364ms22076 KiB
10Elfogadva3/383ms21988 KiB
11Elfogadva2/2104ms25064 KiB
12Elfogadva2/2119ms24808 KiB
13Elfogadva2/2116ms25032 KiB
14Elfogadva2/2107ms25060 KiB
15Elfogadva2/2108ms25228 KiB
16Elfogadva2/2109ms25060 KiB
17Elfogadva2/298ms25028 KiB
18Elfogadva2/2114ms24956 KiB
19Elfogadva2/298ms24848 KiB
20Elfogadva3/3116ms24548 KiB
21Elfogadva3/397ms24808 KiB
22Elfogadva3/3108ms24888 KiB
23Elfogadva3/398ms24964 KiB