87932024-01-31 08:31:16KezdőBináris fa magassága (50 pont)python3Time limit exceeded 20/50587ms13224 KiB
from sys import stdin,stdout

def main():
    N,M = [int(i) for i in stdin.readline().split()]
    k = [2**i for i in range(N+1)]
    f = [0,0]+[1]*k[N]
    h = [0]*k[N-1] + [N-1]*k[N-1]
    u = k[N-1]
##    print(f)

    def holvan(x):
        s = 1
        while x >= k[s]:
            s += 1
        return s

    maxi = N-1
    for i in range(M):
        a,uj = [int(i) for i in stdin.readline().split()]
        b = uj-f[a]
        f[a] = uj
        sor = holvan(a)
        le = N-sor
        maxiuj = N-1
        for i in range(a*k[le],a*k[le]+k[le]):
            h[i] += b
            if h[i] > maxiuj:
                maxiuj = h[i]
        if maxiuj > maxi:
            maxi = maxiuj
        else:
            maxi = max(h[u:])
        stdout.write(str(maxi)+'\n')
main()
SubtaskSumTestVerdictTimeMemory
base20/50
1Accepted0/017ms11272 KiB
2Time limit exceeded0/0549ms6464 KiB
3Accepted2/219ms11868 KiB
4Accepted2/219ms11988 KiB
5Accepted2/221ms12248 KiB
6Accepted2/220ms12740 KiB
7Accepted3/323ms12632 KiB
8Accepted3/324ms12852 KiB
9Accepted3/327ms12736 KiB
10Accepted3/326ms13224 KiB
11Time limit exceeded0/2560ms7044 KiB
12Time limit exceeded0/2568ms7380 KiB
13Time limit exceeded0/2560ms7676 KiB
14Time limit exceeded0/2551ms7600 KiB
15Time limit exceeded0/2572ms7520 KiB
16Time limit exceeded0/2583ms8580 KiB
17Time limit exceeded0/2583ms8760 KiB
18Time limit exceeded0/2587ms8816 KiB
19Time limit exceeded0/2560ms8636 KiB
20Time limit exceeded0/3568ms8052 KiB
21Time limit exceeded0/3540ms8184 KiB
22Time limit exceeded0/3564ms8176 KiB
23Time limit exceeded0/3575ms8244 KiB