Problem:


Score : 700 points

Problem Statement

We have a rooted binary tree with N vertices, where the vertices are numbered 1 to N.
Vertex 1 is the root, and the parent of Vertex i (i \geq 2) is Vertex \left[ \frac{i}{2} \right].

Each vertex has one item in it. The item in Vertex i has a value of V_i and a weight of W_i.
Now, process the following query Q times:

Given are a vertex v of the tree and a positive integer L.
  Let us choose some (possibly none) of the items in v and the ancestors of v so that their total weight is at most L.
  Find the maximum possible total value of the chosen items.

Here, Vertex u is said to be an ancestor of Vertex v when u is an indirect parent of v, that is, there exists a sequence of vertices w_1,w_2,\ldots,w_k (k\geq 2) where w_1=v, w_k=u, and w_{i+1} is the parent of w_i for each i.

Constraints

All values in input are integers.

1 \leq N < 2^{18}

1 \leq Q \leq 10^5

1 \leq V_i \leq 10^5

1 \leq W_i \leq 10^5

For the values v and L given in each query, 1 \leq v \leq N and 1 \leq L \leq 10^5.

Input

Let v_i and L_i be the values v and L given in the i-th query.
Then, Input is given from Standard Input in the following format:

N
V_1 W_1
:
V_N W_N
Q
v_1 L_1
:
v_Q L_Q

Output

For each integer i from 1 through Q,
the i-th line should contain the response to the i-th query.

Sample Input 1

3
1 2
2 3
3 4
3
1 1
2 5
3 5

Sample Output 1

0
3
3

In the first query, we are given only one choice: the item with (V, W)=(1,2). Since L = 1, we cannot actually choose it, so our response should be 0.

In the second query, we are given two choices: the items with (V, W)=(1,2) and (V, W)=(2,3). Since L = 5, we can choose both of them, so our response should be 3.

Sample Input 2

15
123 119
129 120
132 112
126 109
118 103
115 109
102 100
130 120
105 105
132 115
104 102
107 107
127 116
121 104
121 115
8
8 234
9 244
10 226
11 227
12 240
13 237
14 206
15 227

Sample Output 2

256
255
250
247
255
259
223
253



Sample input:
3
1 2
2 3
3 4
3
1 1
2 5
3 5


Sample output:
0
3
3

Submission status: Runtime Error

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N = I()
    n = N.bit_length()
    V = [0]*N; W = [0]*N
    for i in range(N):
        V[i], W[i] = LI()
    q = I()
    Q = [LI()for _ in range(q)]
    ans = [0]*q
    if N<1024:
        S = [[]for _ in range(N)]
        for i in range(N):
            key = i + 1
            cur = []
            while (key > 0):
                cur.append(key-1)
                key //= 2
            dp = {0: 0}
            for loop in range(1 << (len(cur))):
                value, weight = 0, 0
                for j in range(len(cur)):
                    if loop & (1 << j):
                        value += V[cur[j]]
                        weight += W[cur[j]]
                if weight in dp:
                    if dp[weight] < value:
                        dp[weight] = value
                else:
                    dp[weight] = value
            D = sorted(dp.items())
            #print(D)
            now = 0
            for j in range(len(D)):
                if now < D[j][1]:
                    now = D[j][1]
                else:
                    D[j] = [D[j][0],now]
            S[i] = D

        for i,[v,l] in enumerate(Q):
            D = S[v-1]
            for j in range(len(D))[::-1]:
                if D[j][0]<=l:
                    ans[i] = D[j][1]
                    break
        for v in ans:
            print(v)
        return

    half = 1<<9
    S = [[] for _ in range(half)]
    for i in range(half//2,half):
        key = i + 1
        cur = []
        while (key > 0):
            cur.append(key-1)
            key //= 2
        dp = {0: 0}
        for loop in range(1 << (len(cur))):
            value, weight = 0, 0
            for j in range(len(cur)):
                if loop & (1 << j):
                    value += V[cur[j]]
                    weight += W[cur[j]]
            if weight in dp:
                if dp[weight] < value:
                    dp[weight] = value
            else:
                dp[weight] = value
        D = sorted(dp.items())
        now = 0
        for j in range(len(D)):
            if now < D[j][1]:
                now = D[j][1]
            else:
                D[j][1] = now
        S[i] = D

    for i,[v,l] in enumerate(Q):
        v -= 1
        key = v + 1
        if key<=512:
            cur = []
            while (key > 0):
                cur.append(key-1)
                key //= 2
            dp = {0: 0}
            for loop in range(1 << (len(cur))):
                value, weight = 0, 0
                for j in range(len(cur)):
                    if loop & (1 << j):
                        value += V[cur[j]]
                        weight += W[cur[j]]
                if weight in dp:
                    if dp[weight] < value:
                        dp[weight] = value
                else:
                    dp[weight] = value
            D = sorted(dp.items())
            if D[j][0] <= l:
                if ans[i]<D[j][1]:
                    ans[i] = D[j][1]
            continue

        cur = []
        while (key > 512):
            cur.append(key-1)
            key //= 2
        dp = {0: 0}
        for loop in range(1 << (len(cur))):
            value, weight = 0, 0
            for j in range(len(cur)):
                if loop & (1 << j):
                    value += V[cur[j]]
                    weight += W[cur[j]]
            if weight in dp:
                if dp[weight] < value:
                    dp[weight] = value
            else:
                dp[weight] = value
        D = sorted(dp.items())

        #D2 = S[key-1]
        #now = len(D2)-1
        #for j in range(len(D)):
        #    while(now>=0 and D2[now][0]+D[j][0]>l):
        #        now -= 1
        #    if now==-1:
        #        break
        #    if ans[i]<D2[now][1]+D[j][1]:
        #        ans[i] = D2[now][1]+D[j][1]

    for v in ans:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Runtime Error

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N = I()
    n = N.bit_length()
    V = [0]*N; W = [0]*N
    for i in range(N):
        V[i], W[i] = LI()
    q = I()
    Q = [LI()for _ in range(q)]
    ans = [0]*q
    if N<1024:
        S = [[]for _ in range(N)]
        for i in range(N):
            key = i + 1
            cur = []
            while (key > 0):
                cur.append(key-1)
                key //= 2
            dp = {0: 0}
            for loop in range(1 << (len(cur))):
                value, weight = 0, 0
                for j in range(len(cur)):
                    if loop & (1 << j):
                        value += V[cur[j]]
                        weight += W[cur[j]]
                if weight in dp:
                    if dp[weight] < value:
                        dp[weight] = value
                else:
                    dp[weight] = value
            D = sorted(dp.items())
            #print(D)
            now = 0
            for j in range(len(D)):
                if now < D[j][1]:
                    now = D[j][1]
                else:
                    D[j] = [D[j][0],now]
            S[i] = D

        for i,[v,l] in enumerate(Q):
            D = S[v-1]
            for j in range(len(D))[::-1]:
                if D[j][0]<=l:
                    ans[i] = D[j][1]
                    break
        for v in ans:
            print(v)
        return

    half = 1<<9
    S = [[] for _ in range(half)]
    for i in range(half//2,half):
        key = i + 1
        cur = []
        while (key > 0):
            cur.append(key-1)
            key //= 2
        dp = {0: 0}
        for loop in range(1 << (len(cur))):
            value, weight = 0, 0
            for j in range(len(cur)):
                if loop & (1 << j):
                    value += V[cur[j]]
                    weight += W[cur[j]]
            if weight in dp:
                if dp[weight] < value:
                    dp[weight] = value
            else:
                dp[weight] = value
        D = sorted(dp.items())
        now = 0
        for j in range(len(D)):
            if now < D[j][1]:
                now = D[j][1]
            else:
                D[j][1] = now
        S[i] = D

    for i,[v,l] in enumerate(Q):
        v -= 1
        key = v + 1
        cur = []
        if key<=512:
            cur = []
            while (key > 0):
                cur.append(key-1)
                key //= 2
            dp = {0: 0}
            for loop in range(1 << (len(cur))):
                value, weight = 0, 0
                for j in range(len(cur)):
                    if loop & (1 << j):
                        value += V[cur[j]]
                        weight += W[cur[j]]
                if weight in dp:
                    if dp[weight] < value:
                        dp[weight] = value
                else:
                    dp[weight] = value
            D = sorted(dp.items())
            if D[j][0] <= l:
                if ans[i]<D[j][1]:
                    ans[i] = D[j][1]
            continue
        while (key > 512):
            cur.append(key-1)
            key //= 2
        dp = {0: 0}
        for loop in range(1 << (len(cur))):
            value, weight = 0, 0
            for j in range(len(cur)):
                if loop & (1 << j):
                    value += V[cur[j]]
                    weight += W[cur[j]]
            if weight in dp:
                if dp[weight] < value:
                    dp[weight] = value
            else:
                dp[weight] = value
        D = sorted(dp.items())

        D2 = S[key-1]
        now = len(D2)-1
        for j in range(len(D)):
            while(now>=0 and D2[now][0]+D[j][0]>l):
                now -= 1
            if now==-1:
                break
            if ans[i]<D2[now][1]+D[j][1]:
                ans[i] = D2[now][1]+D[j][1]

    for v in ans:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Runtime Error

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    N = I()
    n = N.bit_length()
    V = [0]*N; W = [0]*N
    for i in range(N):
        V[i], W[i] = LI()
    q = I()
    Q = [LI()for _ in range(q)]
    ans = [0]*q
    if N<1024:
        S = [[]for _ in range(N)]
        for i in range(N):
            key = i + 1
            cur = []
            while (key > 0):
                cur.append(key-1)
                key //= 2
            dp = {0: 0}
            for loop in range(1 << (len(cur))):
                value, weight = 0, 0
                for j in range(len(cur)):
                    if loop & (1 << j):
                        value += V[cur[j]]
                        weight += W[cur[j]]
                if weight in dp:
                    if dp[weight] < value:
                        dp[weight] = value
                else:
                    dp[weight] = value
            D = sorted(dp.items())
            #print(D)
            now = 0
            for j in range(len(D)):
                if now < D[j][1]:
                    now = D[j][1]
                else:
                    D[j] = [D[j][0],now]
            S[i] = D

        for i,[v,l] in enumerate(Q):
            D = S[v-1]
            for j in range(len(D))[::-1]:
                if D[j][0]<=l:
                    ans[i] = D[j][1]
                    break
        for v in ans:
            print(v)
        return

    half = 1<<9
    S = [[] for _ in range(half)]
    for i in range(half//2,half):
        key = i + 1
        cur = []
        while (key > 0):
            cur.append(key-1)
            key //= 2
        dp = {0: 0}
        for loop in range(1 << (len(cur))):
            value, weight = 0, 0
            for j in range(len(cur)):
                if loop & (1 << j):
                    value += V[cur[j]]
                    weight += W[cur[j]]
            if weight in dp:
                if dp[weight] < value:
                    dp[weight] = value
            else:
                dp[weight] = value
        D = sorted(dp.items())
        now = 0
        for j in range(len(D)):
            if now < D[j][1]:
                now = D[j][1]
            else:
                D[j][1] = now
        S[i] = D

    for i,[v,l] in enumerate(Q):
        v -= 1
        key = v + 1
        cur = []
        while (key > 512):
            cur.append(key-1)
            key //= 2
        dp = {0: 0}
        for loop in range(1 << (len(cur))):
            value, weight = 0, 0
            for j in range(len(cur)):
                if loop & (1 << j):
                    value += V[cur[j]]
                    weight += W[cur[j]]
            if weight in dp:
                if dp[weight] < value:
                    dp[weight] = value
            else:
                dp[weight] = value
        D = sorted(dp.items())

        D2 = S[key-1]
        now = len(D2)-1
        for j in range(len(D)):
            while(now>=0 and D2[now][0]+D[j][0]>l):
                now -= 1
            if now==-1:
                break
            if ans[i]<D2[now][1]+D[j][1]:
                ans[i] = D2[now][1]+D[j][1]

    for v in ans:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline

def calc():
  MAX=10**5
  LEN=1<<10
  n=int(input())
  arr=[list(map(int,input().split())) for _ in range(n)]
  dp=[None for _ in range(LEN+1)]
  dp[0]=[0]*(MAX+1)
  for i in range(1,min(n,LEN)+1):
    tmp=dp[i>>1][:]
    v,w=arr[i-1]
    for j in range(MAX,w-1,-1):
      if tmp[j]<tmp[j-w]+v:
        tmp[j]=tmp[j-w]+v
    dp[i]=tmp
  q=int(input())
  for _ in range(q):
    v,l=map(int,input().split())
    if v<=LEN:
      print(dp[v][l])
    else:
      vs=[]
      cnt=0
      while v>LEN:
        vs.append(v)
        v>>=1
        cnt+=1
      ans=0
      for i in range(1<<cnt):
        weight=0
        value=0
        for j in range(cnt):
          if i&(1<<j):
            tw,tv=arr[vs[j]]
            weight+=tw
            value+=tv
        if weight>l:
          continue
        ans=max(ans,dp[v][l-weight]+value)
      print(ans)
calc()

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline

def calc():
  MAX=10**5
  n=int(input())
  arr=[list(map(int,input().split())) for _ in range(n)]
  dp=[None for _ in range(1<<9+1)]
  dp[0]=[0]*(MAX+1)
  for i in range(1,min(n,1<<9)+1):
    tmp=dp[i>>1][:]
    v,w=arr[i-1]
    for j in range(MAX,w-1,-1):
      if tmp[j]<tmp[j-w]+v:
        tmp[j]=tmp[j-w]+v
    dp[i]=tmp
  q=int(input())
  for _ in range(q):
    v,l=map(int,input().split())
    if v<=1<<9:
      print(dp[v][l])
    else:
      vs=[]
      cnt=0
      while v>1<<9:
        vs.append(v)
        v=v>>1
        cnt+=1
      ans=0
      for i in range(1<<cnt):
        weight=0
        value=0
        for j in range(cnt):
          if i&(1<<j):
            weight+=arr[vs[j]][1]
            value+=arr[vs[j]][0]
        if weight>l:
          continue
        ans=max(ans,dp[v][l-weight]+value)
      print(ans)
calc()

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline

def calc():
  MAX=10**5
  n=int(input())
  arr=[list(map(int,input().split())) for _ in range(n)]
  dp=[[0]*(MAX+1) for _ in range(1<<9+1)]
  for i in range(1,min(n,1<<9)+1):
    v,w=arr[i-1]
    for j in range(MAX,w-1,-1):
      dp[i][j]=max(dp[i>>1][j],dp[i>>1][j-w]+v)
    for j in range(w-1,-1,-1):
      dp[i][j]=dp[i>>1][j]
  q=int(input())
  for _ in range(q):
    v,l=map(int,input().split())
    if v<=1<<9:
      print(dp[v][l])
    else:
      vs=[]
      cnt=0
      while v>1<<9:
        vs.append(v)
        v=v>>1
        cnt+=1
      ans=0
      for i in range(1<<cnt):
        weight=0
        value=0
        for j in range(cnt):
          if i&(1<<j):
            weight+=arr[vs[j]][1]
            value+=arr[vs[j]][0]
        if weight>l:
          continue
        ans=max(ans,dp[v][l-weight]+value)
      print(ans)
calc()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

#'''
N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]
'''
N = 2 ** 18
vws = [(1, i%10 + 1) for i in range(N)]
#'''
half = 10

n = min(2**half, N)
vws_arr = np.array(vws)

dp = np.zeros((n, 10**5+1), np.int32)
dp[0, vws[0][1]:] = vws[0][0]
for i in range(1, n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[:], i4[:], i4, i4[:])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(len(vs), np.int32)
    weights = np.zeros(len(vs), np.int32)
    for bits in range(1 << len(vs)):
        for i in range(len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    mask = (weights <= L)     
    return np.amax(dp_[L - weights[mask]] + values[mask])

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(np.array(vs, np.int32), np.array(ws, np.int32), L, dp[V]))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]
vs, ws = map(lambda ls: np.array(ls, np.int32), zip(*vws))
Q = int(input())
VLs = np.array(list(map(lambda s: tuple(map(int, s.split())), readlines())), np.int32)

n = min(2**10, N)

@njit("i4[:, :](i4, i4[:], i4[:])", cache = True)
def precompute(n, vs, ws):
    dp = np.zeros((n, 10**5+1), np.int32)
    dp[0, ws[0]:] = vs[0]
    for i in range(1, n):
        v = vs[i]
        w = ws[i]
        dp[i] = dp[(i-1)//2]
        dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])
    return dp

@njit("i4(i4[:], i4[:], i4, i4[:])", cache = True)
def func(vs_part, ws_part, L, dp_):
    bits = np.arange(1 << len(vs_part))
    values = np.zeros_like(bits, np.int32)
    weights = np.zeros_like(bits, np.int32)
    for i in range(len(vs_part)):
        indices = np.nonzero(np.bitwise_and(bits, 1<<i))
        values[indices] += vs_part[i]
        weights[indices] += ws_part[i]

    mask = (weights <= L)     
    return np.amax(dp_[L - weights[mask]] + values[mask])

#@njit("(i4, i4[:], i4[:], i4[:, :])", cache = True)
def main(n, vs, ws, VLs):
    dp = precompute(n, vs, ws)

    for V, L in VLs:
        V -= 1
        if V < n:
            print(dp[V, L])
        else:
            Vs = []
            while V >= n:
                Vs.append(V)
                V = (V-1) // 2
            Vs_arr = np.array(Vs)
            vs_part = vs[Vs_arr]
            ws_part = ws[Vs_arr]
            ans = func(vs_part, ws_part, L, dp[V])
            print(ans)

main(N, vs, ws, VLs)

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline


def mergeup(Av, Aw, vw):
    v, w = vw
    N = len(Av)
    rv, rw = [None]*(2*N), [None]*(2*N)
    idx = 0
    jdx = 0
    for i in range(2*N):
        if idx == N or Aw[idx] > Aw[jdx] + w:
            if Aw[jdx] + w > limit:
                break
            rw[i] = Aw[jdx]+w
            rv[i] = Av[jdx]+v
            jdx += 1
        else:
            rw[i] = Aw[idx]
            rv[i] = Av[idx]
            idx += 1

    return rv, rw

def mergedown(Av, Aw, vw):
    v, w = vw
    N = len(Av)
    resv, resw = [None]*(2*N), [None]*(2*N)

    idx = 0
    jdx = 0
    for i in range(2*N):
        if jdx == N or Aw[idx] <= Aw[jdx] - w:
            resv[i] = Av[idx]
            resw[i] = Aw[idx]
            idx += 1
        else:
            if Aw[jdx] - w < 0:
                jdx += 1
                continue
            resv[i] = Av[jdx] + v
            resw[i] = Aw[jdx] - w
            jdx += 1
    return resv, resw


limit = 10**5
N = int(readline())
VW = [None] + [tuple(map(int, readline().split())) for _ in range(N)]
BS = min(N, 1<<10)
Q = int(readline())
VL = [None] + [tuple(map(int, readline().split())) for _ in range(Q)]


Rv = [[0] for _ in range(BS+1)]
Rw = [[0] for _ in range(BS+1)]
for i in range(1, BS):
    for vm, wm in zip(*mergeup(Rv[i//2], Rw[i//2], VW[i])):
        if Rv[i][-1] < vm:
          Rv[i].append(vm)
          Rw[i].append(wm)
    
ans = [0]*(Q+1)
for i in range(1, Q+1):
    v, l = VL[i]
    Kv, Kw = [0], [l]
    while v >= BS:
        Kv, Kw = mergedown(Kv, Kw, VW[v])
        v >>= 1
    cnt = len(Rv[v])-1
    ctr = 0
    for j in range(len(Kv)-1, -1, -1):
        kv, kw = Kv[j], Kw[j]
        while kw < Rw[v][cnt]:
            cnt -= 1
        ctr = max(ctr, kv+Rv[v][cnt])
    ans[i] = ctr

print('\n'.join(map(str, ans[1:])))

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.readline

def mergeup(Av, Aw, vw):
    v, w = vw
    rv, rw = [], []
    N = len(Av)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if idx == N or Aw[idx] > Aw[jdx] + w:
            rw.append(Aw[jdx]+w)
            rv.append(Av[jdx]+v)
            jdx += 1
        else:
            rw.append(Aw[idx])
            rv.append(Av[idx])
            idx += 1
    return rv, rw

def mergedown(Av, Aw, vw):
    v, w = vw
    resv, resw = [], []
    N = len(Av)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if jdx == N:
            resv.append(Av[idx])
            resw.append(Aw[idx])
            idx += 1
        if Aw[idx] <= Aw[jdx] - w:
            resv.append(Av[idx])
            resw.append(Aw[idx])
            idx += 1
        else:
            if Aw[jdx] - w < 0:
                jdx += 1
                continue
            resv.append(Av[jdx] + v)
            resw.append(Aw[jdx] - w)
            jdx += 1
    return resv, resw

N = int(readline())
VW = [None] + [tuple(map(int, readline().split())) for _ in range(N)]
BS = min(N, 1<<9)
Q = int(readline())
VL = [None] + [tuple(map(int, readline().split())) for _ in range(Q)]


Rv = [[0] for _ in range(BS+1)]
Rw = [[0] for _ in range(BS+1)]
for i in range(1, BS):
    for vm, wm in zip(*mergeup(Rv[i//2], Rw[i//2], VW[i])):
        if Rv[i][-1] < vm:
          Rv[i].append(vm)
          Rw[i].append(wm)
    
ans = [0]*(Q+1)
for i in range(1, Q+1):
    v, l = VL[i]
    Kv, Kw = [0], [l]
    while v >= BS:
        Kv, Kw = mergedown(Kv, Kw, VW[v])
        v >>= 1
    cnt = len(Rv[v])-1
    for j in range(len(Kv)-1, -1, -1):
        kv, kw = Kv[j], Kw[j]
        while kw < Rw[v][cnt]:
            cnt -= 1
        ans[i] = max(ans[i], kv+Rv[v][cnt])

print('\n'.join(map(str, ans[1:])))

Submission status: Runtime Error

Solution code:
import os
from io import BytesIO
readline = BytesIO(os.read(0, os.fstat(0).st_size)).readline

def mergeup(Av, Aw, vw):
    v, w = vw
    rv, rw = [], []
    N = len(Av)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if idx == N or Aw[idx] > Aw[jdx] + w:
            rw.append(Aw[jdx]+w)
            rv.append(Av[jdx]+v)
            jdx += 1
        else:
            rw.append(Aw[idx])
            rv.append(Av[idx])
            idx += 1
    return rv, rw

def mergedown(Av, Aw, vw):
    v, w = vw
    resv, resw = [], []
    N = len(Av)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if jdx == N:
            resv.append(Av[idx])
            resw.append(Aw[idx])
            idx += 1
        if Aw[idx] <= Aw[jdx] - w:
            resv.append(Av[idx])
            resw.append(Aw[idx])
            idx += 1
        else:
            if Aw[jdx] - w < 0:
                jdx += 1
                continue
            resv.append(Av[jdx] + v)
            resw.append(Aw[jdx] - w)
            jdx += 1
    return resv, resw

N = int(readline())
VW = [None] + [tuple(map(int, readline().split())) for _ in range(N)]
BS = min(N, 1<<10)
Q = int(readline())
VL = [None] + [tuple(map(int, readline().split())) for _ in range(Q)]


Rv = [[0] for _ in range(BS+1)]
Rw = [[0] for _ in range(BS+1)]
for i in range(1, BS):
    for vm, wm in zip(*mergeup(Rv[i//2], Rw[i//2], VW[i])):
        if Rv[i][-1] < vm:
          Rv[i].append(vm)
          Rw[i].append(wm)
    
ans = [0]*(Q+1)
for i in range(1, Q+1):
    v, l = VL[i]
    Kv, Kw = [0], [l]
    while v >= BS:
        Kv, Kw = mergedown(Kv, Kw, VW[v])
        v >>= 1
    cnt = len(Rv[v])-1
    for j in range(len(Kv)-1, -1, -1):
        kv, kw = Kv[j], Kw[j]
        while kw < Rw[v][cnt]:
            cnt -= 1
        ans[i] = max(ans[i], kv+Rv[v][cnt])

print('\n'.join(map(str, ans[1:])))

Submission status: Runtime Error

Solution code:
import sys
readline = sys.stdin.buffer.readline

def mergeup(Av, Aw, vw):
    v, w = vw
    rv, rw = [], []
    N = len(Av)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if idx == N or Aw[idx] > Aw[jdx] + w:
            rw.append(Aw[jdx]+w)
            rv.append(Av[jdx]+v)
            jdx += 1
        else:
            rw.append(Aw[idx])
            rv.append(Av[idx])
            idx += 1

    return rv, rw

def mergedown(Av, Aw, vw):
    v, w = vw
    resv, resw = [], []
    N = len(Av)
    idx = 0
    jdx = 0
    for _ in range(2*N):
        if jdx == N:
            resv.append(Av[idx])
            resw.append(Aw[idx])
            idx += 1
            continue
        if Aw[idx] <= Aw[jdx] - w:
            resv.append(Av[idx])
            resw.append(Aw[idx])
            idx += 1
        else:
            if Aw[jdx] - w < 0:
                jdx += 1
                continue
            resv.append(Av[jdx] + v)
            resw.append(Aw[jdx] - w)
            jdx += 1
    return resv, resw

N = int(readline())
VW = [None] + [tuple(map(int, readline().split())) for _ in range(N)]
BS = min(N, 1<<10)
Q = int(readline())
VL = [None] + [tuple(map(int, readline().split())) for _ in range(Q)]


Rv = [[0] for _ in range(BS+1)]
Rw = [[0] for _ in range(BS+1)]
for i in range(1, BS):
    for vm, wm in zip(*mergeup(Rv[i//2], Rw[i//2], VW[i])):
        if Rv[i][-1] < vm:
          Rv[i].append(vm)
          Rw[i].append(wm)
    
ans = [0]*(Q+1)
for i in range(1, Q+1):
    v, l = VL[i]
    Kv, Kw = [0], [l]
    while v >= BS:
        Kv, Kw = mergedown(Kv, Kw, VW[v])
        v >>= 1
    cnt = len(Rv[v])-1
    for j in range(len(Kv)-1, -1, -1):
        kv, kw = Kv[j], Kw[j]
        while kw < Rw[v][cnt]:
            acnt -= 1
        ans[i] = max(ans[i], kv+Rv[v][cnt])

print('\n'.join(map(str, ans[1:])))