Submission #11,877

2024-11-13 18:57:29

pypy3

Accepted 50/50

119ms

25228 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])

	Sum	Test	Verdict		Time	Memory
base	50/50
		1	Accepted	0/0	43ms	19476 KiB
		2	Accepted	0/0	100ms	25012 KiB
		3	Accepted	2/2	59ms	21392 KiB
		4	Accepted	2/2	71ms	21744 KiB
		5	Accepted	2/2	86ms	21840 KiB
		6	Accepted	2/2	74ms	22476 KiB
		7	Accepted	3/3	71ms	22232 KiB
		8	Accepted	3/3	71ms	22208 KiB
		9	Accepted	3/3	64ms	22076 KiB
		10	Accepted	3/3	83ms	21988 KiB
		11	Accepted	2/2	104ms	25064 KiB
		12	Accepted	2/2	119ms	24808 KiB
		13	Accepted	2/2	116ms	25032 KiB
		14	Accepted	2/2	107ms	25060 KiB
		15	Accepted	2/2	108ms	25228 KiB
		16	Accepted	2/2	109ms	25060 KiB
		17	Accepted	2/2	98ms	25028 KiB
		18	Accepted	2/2	114ms	24956 KiB
		19	Accepted	2/2	98ms	24848 KiB
		20	Accepted	3/3	116ms	24548 KiB
		21	Accepted	3/3	97ms	24808 KiB
		22	Accepted	3/3	108ms	24888 KiB
		23	Accepted	3/3	98ms	24964 KiB