Problem p03176 (python)

Fixed submission:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]



class Node:
    def __init__(self,s,e):
        self.start=s
        self.end=e
        self.val = 0
        self.left=None
        self.right=None
 
def build(nums,l,r):
    if l == r:
        temp = Node(l,l)
        temp.val = nums[l]
    else:
        mid=(l+r)>>1
        temp=Node(l,r)
        temp.left=build(nums,l,mid)
        temp.right=build(nums,mid+1,r)
        temp.val = max(temp.left.val,temp.right.val)
    return temp

def update(root,start,value):
    if root.start == start == root.end:
        root.val = value
    elif root.start <= start and root.end >= start:
        update(root.left,start,value)
        update(root.right,start,value)
        root.val = max(root.left.val,root.right.val)





def query(root,start,end):
    if root.start>=start and root.end<=end:return root.val
    elif root.start>end or root.end<start:return -float('inf')
    else:
        temp1 = query(root.left,start,end)
        temp2 = query(root.right,start,end)
        return max(temp1,temp2)
        

    

N = val()
height = li()
beauty = li()

fenwick = build([0] * (N + 1), 0, N)


ans = 0

for i in range(N):
    curr = beauty[i] + query(fenwick, 0, height[i])
    ans = max(ans, curr)
    update(fenwick, height[i], curr)

print(ans)

Buggy submission (verdict: Runtime Error):
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
 
M = mod = 10**9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


class Node:
    def __init__(self,s,e):
        self.start=s
        self.end=e
        self.val = 0
        self.left=None
        self.right=None
 
def build(nums,l,r):
    if l == r:
        temp = Node(l,l)
        temp.val = 0
    else:
        mid=(l+r)>>1
        temp=Node(l,r)
        temp.left=build(nums,l,mid)
        temp.right=build(nums,mid+1,r)
        temp.val = temp.left.val + temp.right.val
    return temp
 
def update(root,start,va):
    if root.start==root.end==start:
        root.val = va
    elif root.start<=start and root.end>=start:

        root.left=update(root.left,start,va)
        root.right=update(root.right,start,va)
        root.val = max(root.left.val,root.right.val)
    return root
    
def query(root,start,end):
    if root.start>=start and root.end<=end:return root.val
    elif root.start>end or root.end<start:return 0
    else:
        temp1 = query(root.left,start,end)
        temp2 = query(root.right,start,end)
        return max(temp1,temp2)
        

root = build([],0,200005)
n = val()
h = li()
a = li()
ans = 0

for i in range(n):
    curr = query(root,-1,h[i])
    temp = curr + a[i]
    ans = max(ans,temp)
    root = update(root,h[i],temp)
print(ans)from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline
 
M = mod = 10**9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]


class Node:
    def __init__(self,s,e):
        self.start=s
        self.end=e
        self.val = 0
        self.left=None
        self.right=None
 
def build(nums,l,r):
    if l == r:
        temp = Node(l,l)
        temp.val = 0
    else:
        mid=(l+r)>>1
        temp=Node(l,r)
        temp.left=build(nums,l,mid)
        temp.right=build(nums,mid+1,r)
        temp.val = temp.left.val + temp.right.val
    return temp
 
def update(root,start,va):
    if root.start==root.end==start:
        root.val = va
    elif root.start<=start and root.end>=start:

        root.left=update(root.left,start,va)
        root.right=update(root.right,start,va)
        root.val = max(root.left.val,root.right.val)
    return root
    
def query(root,start,end):
    if root.start>=start and root.end<=end:return root.val
    elif root.start>end or root.end<start:return 0
    else:
        temp1 = query(root.left,start,end)
        temp2 = query(root.right,start,end)
        return max(temp1,temp2)
        

root = build([],0,200005)
n = val()
h = li()
a = li()
ans = 0

for i in range(n):
    curr = query(root,-1,h[i])
    temp = curr + a[i]
    ans = max(ans,temp)
    root = update(root,h[i],temp)
print(ans)