Problem:


Score : 100 points

Problem Statement

There are N flowers arranged in a row.
For each i (1 \leq i \leq N), the height and the beauty of the i-th flower from the left is h_i and a_i, respectively.
Here, h_1, h_2, \ldots, h_N are all distinct.

Taro is pulling out some flowers so that the following condition is met:

The heights of the remaining flowers are monotonically increasing from left to right.

Find the maximum possible sum of the beauties of the remaining flowers.

Constraints

All values in input are integers.

1 \leq N \leq 2 × 10^5

1 \leq h_i \leq N

h_1, h_2, \ldots, h_N are all distinct.

1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
h_1 h_2 \ldots h_N
a_1 a_2 \ldots a_N

Output

Print the maximum possible sum of the beauties of the remaining flowers.

Sample Input 1

4
3 1 4 2
10 20 30 40

Sample Output 1

60

We should keep the second and fourth flowers from the left.
Then, the heights would be 1, 2 from left to right, which is monotonically increasing, and the sum of the beauties would be 20 + 40 = 60.

Sample Input 2

1
1
10

Sample Output 2

10

The condition is met already at the beginning.

Sample Input 3

5
1 2 3 4 5
1000000000 1000000000 1000000000 1000000000 1000000000

Sample Output 3

5000000000

The answer may not fit into a 32-bit integer type.

Sample Input 4

9
4 2 5 8 3 6 1 7 9
6 8 8 4 6 3 5 7 5

Sample Output 4

31

We should keep the second, third, sixth, eighth and ninth flowers from the left.



Sample input:
4
3 1 4 2
10 20 30 40


Sample output:
60

Submission status: Time Limit Exceeded

Solution code:
# EDPC Q - Flowers
# 重み付きのLISと言って良いような問題
# これは、LISのdpを少し改造すれば解ける

import numpy as np


## test data
# 4
# 3 1 4 2
# 10 20 30 40
## ans=60

# import bisect

class SegTree:
	def __init__(self,size,func,init_val,undef):
		self.specSize = size
		self.datSize = 1
		self.compareFunc = func		# suppose to min or max
		self.INIT_VAL = init_val	# 0 etc
		self.UNDEFINED_VAL = undef	# 1e18 -1e18 etc
		while self.datSize < size: self.datSize *= 2

		# the tree is implemented by sequencial list
		# self.datTree = [self.INIT_VAL for _ in range(2*self.datSize+1)]
		self.datTree = np.full(2*self.datSize+1,self.INIT_VAL,int)

	def update(self, i, val ):
		i -= 1	# 1-orderで指定され、内部では0-Order想定?
		i += (self.datSize - 1)
		# print("upd",i,val)
		self.datTree[i] = val
		while 0 < i:
			i = (i-1) >> 1	# (i-1)//2
			self.datTree[i] = self.compareFunc( self.datTree[i*2+1], self.datTree[i*2+2] )
			# print("upd",i,self.datTree[i])

	def query(self,a,b):
		return self.query_2(a,b,0,0,self.datSize)

	def query_(self,a,b,i,l,r):
		""" get minimun/maximum value of range[a,b)
		all 1-indexed
		i is the root vertex of search 
		l,r is range of the root vertex
		"""
		if r <= a or b <= l:
			# (a,b) and (l,r) is not intersected
			return self.UNDEFINED_VAL

		if a <= l and r <= b:
			# i is index required
			return self.datTree[i]
		else:
			# search children
			m = (l+r) >> 1 #(l+r) // 2
			# vl = self.query_(a, b, i*2 + 1, l, m )
			# vr = self.query_(a, b, i*2 + 2, m, r )
			vl = self.query_(a, b, (i << 1) + 1, l, m )
			vr = self.query_(a, b, (i << 1) + 2, m, r )
			return self.compareFunc(vl,vr)

	def query_2(self,a,b,i,l,r):
		""" get minimun/maximum value of range[a,b)
		all 1-indexed
		i is the root vertex of search 
		l,r is range of the root vertex
		"""
		ret = self.UNDEFINED_VAL

		a += self.datSize
		b += self.datSize
		while a < b:
			if b & 1:
				b -= 1
				ret = self.compareFunc(ret, self.datTree[b-1])

			if a & 1:
				ret = self.compareFunc(ret, self.datTree[a-1])
				a += 1

			a >>= 1; b >>= 1

		return ret
		# if r <= a or b <= l:
		# 	# (a,b) and (l,r) is not intersected
		# 	return self.UNDEFINED_VAL

		# if a <= l and r <= b:
		# 	# i is index required
		# 	return self.datTree[i]
		# else:
		# 	# search children
		# 	m = (l+r) >> 1 #(l+r) // 2
		# 	# vl = self.query_(a, b, i*2 + 1, l, m )
		# 	# vr = self.query_(a, b, i*2 + 2, m, r )
		# 	vl = self.query_(a, b, (i << 1) + 1, l, m )
		# 	vr = self.query_(a, b, (i << 1) + 2, m, r )
		# 	return self.compareFunc(vl,vr)


def LongestIncreaseSeaquence(H,A):
	# === Coordinate compression ===
	# unique and sort asc
	N = len(H)
	# sortedA = sorted(list(set(A)))
	lis = 0

	# === Range Maximum Query ===
	# ここでは、各要素iに、最後の値がiの時のLISを登録
	tree = SegTree(N,max,0,-1e18)
	for n in range(N):

		# i=bisect.bisect_left(sortedA,A[n])

		maxValOfCurrentRange = tree.query(0,H[n])
		# valOfNext = tree.query(H[n],H[n]+1)

		# # i+=1

		# if valOfNext < maxValOfCurrentRange + A[n]:
		# print( H[n], maxValOfCurrentRange + A[n] )
		# tree.debugPrint()
		tree.update( H[n], maxValOfCurrentRange + A[n] )

	lis = tree.query(0,N+1)
	return lis


def main():
	N = int(input())
	# 高さは、N以下で全部違うらしい
	H = list(map(int, input().split()))
	A = list(map(int, input().split()))
	# A = [ int(input()) for _ in range(N)]
	print(LongestIncreaseSeaquence(H,A))



if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
# EDPC Q - Flowers
# 重み付きのLISと言って良いような問題
# これは、LISのdpを少し改造すれば解ける

## test data
# 4
# 3 1 4 2
# 10 20 30 40
## ans=60

# import bisect

class SegTree:
	def __init__(self,size,func,init_val,undef):
		self.specSize = size
		self.datSize = 1
		self.compareFunc = func		# suppose to min or max
		self.INIT_VAL = init_val	# 0 etc
		self.UNDEFINED_VAL = undef	# 1e18 -1e18 etc
		while self.datSize < size: self.datSize *= 2

		# the tree is implemented by sequencial list
		self.datTree = [self.INIT_VAL for _ in range(2*self.datSize+1)]

	def update(self, i, val ):
		i -= 1	# 1-orderで指定され、内部では0-Order想定?
		i += (self.datSize - 1)
		# print("upd",i,val)
		self.datTree[i] = val
		while 0 < i:
			i = (i-1) >> 1	# (i-1)//2
			self.datTree[i] = self.compareFunc( self.datTree[i*2+1], self.datTree[i*2+2] )
			# print("upd",i,self.datTree[i])

	def query(self,a,b):
		return self.query_2(a,b,0,0,self.datSize)

	def query_(self,a,b,i,l,r):
		""" get minimun/maximum value of range[a,b)
		all 1-indexed
		i is the root vertex of search 
		l,r is range of the root vertex
		"""
		if r <= a or b <= l:
			# (a,b) and (l,r) is not intersected
			return self.UNDEFINED_VAL

		if a <= l and r <= b:
			# i is index required
			return self.datTree[i]
		else:
			# search children
			m = (l+r) >> 1 #(l+r) // 2
			# vl = self.query_(a, b, i*2 + 1, l, m )
			# vr = self.query_(a, b, i*2 + 2, m, r )
			vl = self.query_(a, b, (i << 1) + 1, l, m )
			vr = self.query_(a, b, (i << 1) + 2, m, r )
			return self.compareFunc(vl,vr)

	def query_2(self,a,b,i,l,r):
		""" get minimun/maximum value of range[a,b)
		all 1-indexed
		i is the root vertex of search 
		l,r is range of the root vertex
		"""
		ret = self.UNDEFINED_VAL

		a += self.datSize
		b += self.datSize
		while a < b:
			if b & 1:
				b -= 1
				ret = self.compareFunc(ret, self.datTree[b-1])

			if a & 1:
				ret = self.compareFunc(ret, self.datTree[a-1])
				a += 1

			a >>= 1; b >>= 1

		return ret
		# if r <= a or b <= l:
		# 	# (a,b) and (l,r) is not intersected
		# 	return self.UNDEFINED_VAL

		# if a <= l and r <= b:
		# 	# i is index required
		# 	return self.datTree[i]
		# else:
		# 	# search children
		# 	m = (l+r) >> 1 #(l+r) // 2
		# 	# vl = self.query_(a, b, i*2 + 1, l, m )
		# 	# vr = self.query_(a, b, i*2 + 2, m, r )
		# 	vl = self.query_(a, b, (i << 1) + 1, l, m )
		# 	vr = self.query_(a, b, (i << 1) + 2, m, r )
		# 	return self.compareFunc(vl,vr)


def LongestIncreaseSeaquence(H,A):
	# === Coordinate compression ===
	# unique and sort asc
	N = len(H)
	# sortedA = sorted(list(set(A)))
	lis = 0

	# === Range Maximum Query ===
	# ここでは、各要素iに、最後の値がiの時のLISを登録
	tree = SegTree(N,max,0,-1e18)
	for n in range(N):

		# i=bisect.bisect_left(sortedA,A[n])

		maxValOfCurrentRange = tree.query(0,H[n])
		# valOfNext = tree.query(H[n],H[n]+1)

		# # i+=1

		# if valOfNext < maxValOfCurrentRange + A[n]:
		# print( H[n], maxValOfCurrentRange + A[n] )
		# tree.debugPrint()
		tree.update( H[n], maxValOfCurrentRange + A[n] )

	lis = tree.query(0,N+1)
	return lis


def main():
	N = int(input())
	# 高さは、N以下で全部違うらしい
	H = list(map(int, input().split()))
	A = list(map(int, input().split()))
	# A = [ int(input()) for _ in range(N)]
	print(LongestIncreaseSeaquence(H,A))



if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
# EDPC Q - Flowers
# 重み付きのLISと言って良いような問題
# これは、LISのdpを少し改造すれば解ける

## test data
# 4
# 3 1 4 2
# 10 20 30 40
## ans=60

import bisect

class SegTree:
	def __init__(self,size,func,init_val,undef):
		self.specSize = size
		self.datSize = 1
		self.compareFunc = func		# suppose to min or max
		self.INIT_VAL = init_val	# 0 etc
		self.UNDEFINED_VAL = undef	# 1e18 -1e18 etc
		while self.datSize < size: self.datSize *= 2

		# the tree is implemented by sequencial list
		self.datTree = [self.INIT_VAL for _ in range(2*self.datSize+1)]

	def update(self, i, val ):
		i -= 1	# 1-orderで指定され、内部では0-Order想定?
		i += (self.datSize - 1)
		# print("upd",i,val)
		self.datTree[i] = val
		while 0 < i:
			i = (i-1) >> 1	# (i-1)//2
			self.datTree[i] = self.compareFunc( self.datTree[i*2+1], self.datTree[i*2+2] )
			# print("upd",i,self.datTree[i])

	def query(self,a,b):
		return self.query_(a,b,0,0,self.datSize)

	def query_(self,a,b,i,l,r):
		""" get minimun/maximum value of range[a,b)
		all 1-indexed
		i is the root vertex of search 
		l,r is range of the root vertex
		"""
		if r <= a or b <= l:
			# (a,b) and (l,r) is not intersected
			return self.UNDEFINED_VAL

		if a <= l and r <= b:
			# i is index required
			return self.datTree[i]
		else:
			# search children
			m = (l+r) >> 1 #(l+r) // 2
			# vl = self.query_(a, b, i*2 + 1, l, m )
			# vr = self.query_(a, b, i*2 + 2, m, r )
			vl = self.query_(a, b, (i << 1) + 1, l, m )
			vr = self.query_(a, b, (i << 1) + 2, m, r )
			return self.compareFunc(vl,vr)

def LongestIncreaseSeaquence(H,A):
	# === Coordinate compression ===
	# unique and sort asc
	N = len(H)
	# sortedA = sorted(list(set(A)))
	lis = 0

	# === Range Maximum Query ===
	# ここでは、各要素iに、最後の値がiの時のLISを登録
	tree = SegTree(N,max,0,-1e18)
	for n in range(N):

		# i=bisect.bisect_left(sortedA,A[n])

		maxValOfCurrentRange = tree.query(0,H[n])
		# valOfNext = tree.query(H[n],H[n]+1)

		# # i+=1

		# if valOfNext < maxValOfCurrentRange + A[n]:
		# print( H[n], maxValOfCurrentRange + A[n] )
		# tree.debugPrint()
		tree.update( H[n], maxValOfCurrentRange + A[n] )

	lis = tree.query(0,N+1)
	return lis


def main():
	N = int(input())
	# 高さは、N以下で全部違うらしい
	H = list(map(int, input().split()))
	A = list(map(int, input().split()))
	# A = [ int(input()) for _ in range(N)]
	print(LongestIncreaseSeaquence(H,A))



if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
# EDPC Q - Flowers
# 重み付きのLISと言って良いような問題
# これは、LISのdpを少し改造すれば解ける

## test data
# 4
# 3 1 4 2
# 10 20 30 40
## ans=60

import bisect

class SegTree:
	def __init__(self,size,func,init_val,undef):
		self.specSize = size
		self.datSize = 1
		self.compareFunc = func		# suppose to min or max
		self.INIT_VAL = init_val	# 0 etc
		self.UNDEFINED_VAL = undef	# 1e18 -1e18 etc
		while self.datSize < size: self.datSize *= 2

		# the tree is implemented by sequencial list
		self.datTree = [self.INIT_VAL for _ in range(2*self.datSize+1)]

	def update(self, i, val ):
		i -= 1	# 1-orderで指定され、内部では0-Order想定?
		i += (self.datSize - 1)
		# print("upd",i,val)
		self.datTree[i] = val
		while 0 < i:
			i = (i-1)//2
			self.datTree[i] = self.compareFunc( self.datTree[i*2+1], self.datTree[i*2+2] )
			# print("upd",i,self.datTree[i])

	def query(self,a,b):
		return self.query_(a,b,0,0,self.datSize)

	def query_(self,a,b,i,l,r):
		""" get minimun/maximum value of range[a,b)
		i is the root vertex of search 
		l,r is range of the root vertex
		"""
		if r <= a or b <= l:
			# (a,b) and (l,r) is not intersected
			return self.UNDEFINED_VAL

		if a <= l and r <= b:
			# i is index required
			return self.datTree[i]
		else:
			# search children
			m = (l+r) // 2
			vl = self.query_(a, b, i*2 + 1, l, m )
			vr = self.query_(a, b, i*2 + 2, m, r )
			return self.compareFunc(vl,vr)

	def debugPrint(self):
		print("=== seg tree debug print start ===")
		print(self.datTree)
		print("== root ==")
		print(self.datTree[0])
		print("== leaf ==")
		print(self.datTree[self.datSize-1:])
		print("=== seg tree debug print end ===")

def LongestIncreaseSeaquence(H,A):
	# === Coordinate compression ===
	# unique and sort asc
	N = len(H)
	# sortedA = sorted(list(set(A)))
	lis = 0

	# === Range Maximum Query ===
	# ここでは、各要素iに、最後の値がiの時のLISを登録
	tree = SegTree(N,max,0,-1e18)
	for n in range(N):

		# i=bisect.bisect_left(sortedA,A[n])

		maxValOfCurrentRange = tree.query(0,H[n])
		# valOfNext = tree.query(H[n],H[n]+1)

		# # i+=1

		# if valOfNext < maxValOfCurrentRange + A[n]:
		# print( H[n], maxValOfCurrentRange + A[n] )
		# tree.debugPrint()
		tree.update( H[n], maxValOfCurrentRange + A[n] )

	lis = tree.query(0,N+1)
	return lis


def main():
	N = int(input())
	# 高さは、N以下で全部違うらしい
	H = list(map(int, input().split()))
	A = list(map(int, input().split()))
	# A = [ int(input()) for _ in range(N)]
	print(LongestIncreaseSeaquence(H,A))



if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
# EDPC Q - Flowers
# 重み付きのLISと言って良いような問題
# これは、LISのdpを少し改造すれば解ける

## test data
## 5
## 4 2 3 1 5
## ans=3

import bisect

class SegTree:
	def __init__(self,size,func,init_val,undef):
		self.specSize = size
		self.datSize = 1
		self.compareFunc = func		# suppose to min or max
		self.INIT_VAL = init_val	# 0 etc
		self.UNDEFINED_VAL = undef	# 1e18 -1e18 etc
		while self.datSize < size: self.datSize *= 2

		# the tree is implemented by sequencial list
		self.datTree = [self.INIT_VAL for _ in range(2*self.datSize+1)]

	def update(self, i, val ):
		i -= 1	# 1-orderで指定され、内部では0-Order想定?
		i += (self.datSize - 1)
		# print("upd",i,val)
		self.datTree[i] = val
		while 0 < i:
			i = (i-1)//2
			self.datTree[i] = self.compareFunc( self.datTree[i*2+1], self.datTree[i*2+2] )
			# print("upd",i,self.datTree[i])

	def query(self,a,b):
		return self.query_(a,b,0,0,self.datSize)

	def query_(self,a,b,i,l,r):
		""" get minimun/maximum value of range[a,b)
		i is the root vertex of search 
		l,r is range of the root vertex
		"""
		if r <= a or b <= l:
			# (a,b) and (l,r) is not intersected
			return self.UNDEFINED_VAL

		if a <= l and r <= b:
			# i is index required
			return self.datTree[i]
		else:
			# search children
			m = (l+r) // 2
			vl = self.query_(a, b, i*2 + 1, l, m )
			vr = self.query_(a, b, i*2 + 2, m, r )
			return self.compareFunc(vl,vr)

	def debugPrint(self):
		print("=== seg tree debug print start ===")
		print(self.datTree)
		print("== root ==")
		print(self.datTree[0])
		print("== leaf ==")
		print(self.datTree[self.datSize-1:])
		print("=== seg tree debug print end ===")

def LongestIncreaseSeaquence(H,A):
	# === Coordinate compression ===
	# unique and sort asc
	N = len(H)
	# sortedA = sorted(list(set(A)))
	lis = 0

	# === Range Maximum Query ===
	# ここでは、各要素iに、最後の値がiの時のLISを登録
	tree = SegTree(N,max,0,-1e18)
	for n in range(N):

		# i=bisect.bisect_left(sortedA,A[n])

		maxValOfCurrentRange = tree.query(0,H[n])
		valOfNext = tree.query(H[n],H[n]+1)

		# i+=1

		if valOfNext < maxValOfCurrentRange + A[n]:
			# print( H[n], maxValOfCurrentRange + A[n] )
			# tree.debugPrint()
			tree.update( H[n], maxValOfCurrentRange + A[n] )

	lis = tree.query(0,N+1)
	return lis


def main():
	N = int(input())
	# 高さは、N以下で全部違うらしい
	H = list(map(int, input().split()))
	A = list(map(int, input().split()))
	# A = [ int(input()) for _ in range(N)]
	print(LongestIncreaseSeaquence(H,A))



if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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

# セグメント木のクラス
# 後日遅延評価なども取り入れていきたいが、とりあえず
# 基本的なところだけを分かりやすい形で組んでみたもの
# length:データ部の長さ depth:構造全体の深さ
# offset:上位構造の長さ tree:全体リスト
 
class Segment_Tree:
    # コンストラクタ。リストもしくは要素数にて初期化。
    # デフォルトでは最小値を求めるが、op(operation=演算内容、デフォルトは最小値)、
    # ie(identity element単位元)を指定することも可能(f.e: op=operator.add, ie=0)
    def __init__(self, arg1, op=lambda x, y:x if x < y else y, ie=math.inf):
        self.op = op
        self.ie = ie
 
        if type(arg1) == int:
            default_list = []
            self.length = arg1
        else:
            default_list = list(arg1)
            self.length = len(arg1)
 
        # 全体の深さ、上位構造分のオフセットを求める
        self.depth = 0
        self.offset = 1
        while self.offset < self.length:
            self.depth += 1
            self.offset *= 2
 
        # 木の初期化。構造は1-indexedで使用していくことにする
        self.tree = [self.ie] * (self.offset * 2)
        if default_list:
            self.tree[self.offset:self.offset+self.length] = default_list
            self.refresh()
 
    # 全体の再計算(愚直に……)
    def refresh(self):
        for idx in range(self.offset - 1, 0, -1):
            self.tree[idx] = self.op(self.tree[idx*2], self.tree[idx*2+1])
 
    # 値のセット、及び関連する部分の再計算
    def set(self, idx, value):
        idx = idx + self.offset
        self.tree[idx] = value
        while idx > 1:
            idx //= 2
            old = self.tree[idx]
            new = self.op(self.tree[idx*2], self.tree[idx*2+1])
            # 変更がなくなれば打ち切り
            if old == new:
                break
            else:
                self.tree[idx] = new
        
    # 半開区間[left, right)における欲しい値(アレっすよ、アレ)を求める
    def find(self, left, right):
        # 区間がおかしなときは、エラー代わりに単位元とかでも返しておく
        if left >= right:
            return self.ie
        
        # 左端と右端から上位を見ていく
        result = self.ie
        left = left + self.offset
        right = right + self.offset - 1
 
        # 左端と右端が重なるとこまで演算
        while left <= right:
            # 左端は、自身が親の右側の子の時(=ノード番号が奇数のとき)にだけ演算する
            if left & 1:
                result = self.op(result, self.tree[left])
            # 一段上に移動
            left = (left + 1) // 2
 
            # 右端は、自身が親の左側の(以下略
            if not right & 1:
                result = self.op(result, self.tree[right])
            right = (right - 1) // 2
       
        return result
    
    # データ領域の値をindexに応じて返す
    def get(self, x):
        return self.tree[x+self.offset]
 
    # 全領域を対象にした計算値を返す
    def find_all(self):
        return self.tree[1]
    
    # 保持している値全体を返す（デバッグ用？）
    def show_tree(self):
        print(self.tree)
 
def main():
    N = int(input())
    h_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))
 
    dpt = Segment_Tree(N+1, op=lambda x,y:x if x>y else y, ie=0)
 
    for height, beauty in zip(h_list, b_list):
        max_to_left = dpt.find(0, height)
        dpt.set(height, max(dpt.get(height), max_to_left + beauty))
    
    print(dpt.find_all())
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 演算内容、単位元の必要に応じて(コンストラクタ参照)
import math

# セグメント木のクラス
# 後日遅延評価なども取り入れていきたいが、とりあえず
# 基本的なところだけを分かりやすい形で組んでみたもの
# length:データ部の長さ depth:構造全体の深さ
# offset:上位構造の長さ tree:全体リスト

class Segment_Tree:
    # コンストラクタ。リストもしくは要素数にて初期化。
    # デフォルトでは最小値を求めるが、op(operation=演算内容、デフォルトは最小値)、
    # ie(identity element単位元)を指定することも可能(f.e: op=operator.add, ie=0)
    def __init__(self, arg1, op=lambda x, y:x if x < y else y, ie=math.inf):
        self.op = op
        self.ie = ie

        if type(arg1) == int:
            default_list = []
            self.length = arg1
        else:
            default_list = list(arg1)
            self.length = len(arg1)

        # 全体の深さ、上位構造分のオフセットを求める
        self.depth = 0
        self.offset = 1
        while self.offset < self.length:
            self.depth += 1
            self.offset *= 2

        # 木の初期化。構造は1-indexedで使用していくことにする
        self.tree = [self.ie] * (self.offset * 2)
        if default_list:
            self.tree[self.offset:self.offset+self.length] = default_list
            self.refresh()

    # 全体の再計算(愚直に……)
    def refresh(self):
        for idx in range(self.offset - 1, 0, -1):
            self.tree[idx] = self.op(self.tree[idx*2], self.tree[idx*2+1])

    # 値のセット、及び関連する部分の再計算
    def set(self, idx, value):
        idx = idx + self.offset
        self.tree[idx] = value
        while idx > 1:
            idx //= 2
            old = self.tree[idx]
            new = self.op(self.tree[idx*2], self.tree[idx*2+1])
            # 変更がなくなれば打ち切り
            if old == new:
                break
            else:
                self.tree[idx] = new
        
    # 半開区間[left, right)における欲しい値(アレっすよ、アレ)を求める
    def find(self, left, right):
        # 区間がおかしなときは、エラー代わりに単位元とかでも返しておく
        if left >= right:
            return self.ie
        
        # 左端と右端から上位を見ていく
        result = self.ie
        left = left + self.offset
        right = right + self.offset - 1

        # 左端と右端が重なるとこまで演算
        while left <= right:
            # 左端は、自身が親の右側の子の時(=ノード番号が奇数のとき)にだけ演算する
            if left & 1:
                result = self.op(result, self.tree[left])
            # 一段上に移動
            left = (left + 1) // 2

            # 右端は、自身が親の左側の(以下略
            if not right & 1:
                result = self.op(result, self.tree[right])
            right = (right - 1) // 2
       
        return result
    
    # データ領域の値をindexに応じて返す
    def get(self, x):
        return self.tree[x+self.offset]

    # 全領域を対象にした計算値を返す
    def find_all(self):
        return self.tree[1]
    
    # 保持している値全体を返す（デバッグ用？）
    def show_tree(self):
        print(self.tree)

def main():
    N = int(input())
    h_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))

    dpt = Segment_Tree(N+1, op=lambda x,y:x if x>y else y, ie=0)

    for height, beauty in zip(h_list, b_list):
        max_to_left = dpt.find(0, height)
        dpt.set(height, max(dpt.get(height), max_to_left + beauty))
    
    print(dpt.find_all())

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 演算内容、単位元の必要に応じて(コンストラクタ参照)
import math

# セグメント木のクラス
# 後日遅延評価なども取り入れていきたいが、とりあえず
# 基本的なところだけを分かりやすい形で組んでみたもの
# length:データ部の長さ depth:構造全体の深さ
# offset:上位構造の長さ tree:全体リスト

class Segment_Tree:
    # コンストラクタ。リストもしくは要素数にて初期化。
    # デフォルトでは最小値を求めるが、op(operation=演算内容、デフォルトは最小値)、
    # ie(identity element単位元)を指定することも可能(f.e: op=operator.add, ie=0)
    def __init__(self, arg1, op=lambda x, y:x if x < y else y, ie=math.inf):
        self.op = op
        self.ie = ie

        if type(arg1) == int:
            default_list = []
            self.length = arg1
        else:
            default_list = list(arg1)
            self.length = len(arg1)

        # 全体の深さ、上位構造分のオフセットを求める
        self.depth = 0
        self.offset = 1
        while self.offset < self.length:
            self.depth += 1
            self.offset *= 2

        # 木の初期化。構造は1-indexedで使用していくことにする
        self.tree = [self.ie] * (self.offset * 2)
        if default_list:
            self.tree[self.offset:self.offset+self.length] = default_list
            self.refresh()

    # 全体の再計算(愚直に……)
    def refresh(self):
        for idx in range(self.offset - 1, 0, -1):
            self.tree[idx] = self.op(self.tree[idx*2], self.tree[idx*2+1])

    # 値のセット、及び関連する部分の再計算
    def set(self, idx, value):
        idx = idx + self.offset
        self.tree[idx] = value
        while idx > 1:
            idx //= 2
            self.tree[idx] = self.op(self.tree[idx*2], self.tree[idx*2+1])
        
    # 半開区間[left, right)における欲しい値(アレっすよ、アレ)を求める
    def find(self, left, right):
        # 区間がおかしなときは、エラー代わりに単位元とかでも返しておく
        if left >= right:
            return self.ie
        
        # 左端と右端から上位を見ていく
        result = self.ie
        left = left + self.offset
        right = right + self.offset - 1

        # 左端と右端が重なるとこまで演算
        while left <= right:
            # 左端は、自身が親の右側の子の時(=ノード番号が奇数のとき)にだけ演算する
            if left % 2 == 1:
                result = self.op(result, self.tree[left])
            # 一段上に移動
            left = (left + 1) // 2

            # 右端は、自身が親の左側の(以下略
            if right % 2 == 0:
                result = self.op(result, self.tree[right])
            right = (right - 1) // 2
       
        return result
    
    # データ領域の値をindexに応じて返す
    def get(self, x):
        return self.tree[x+self.offset]

    # 全領域を対象にした計算値を返す
    def find_all(self):
        return self.tree[1]
    
    # 保持している値全体を返す（デバッグ用？）
    def show_tree(self):
        print(self.tree)

def main():
    N = int(input())
    h_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))

    dpt = Segment_Tree(N+1, op=lambda x,y:x if x>y else y, ie=0)

    for height, beauty in zip(h_list, b_list):
        max_to_left = dpt.find(0, height)
        dpt.set(height, max(dpt.get(height), max_to_left + beauty))
    
    print(dpt.find_all())

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 演算内容、単位元の必要に応じて(コンストラクタ参照)
import math

# セグメント木のクラス
# 後日遅延評価なども取り入れていきたいが、とりあえず
# 基本的なところだけを分かりやすい形で組んでみたもの
# length:データ部の長さ depth:構造全体の深さ
# offset:上位構造の長さ tree:全体リスト

class Segment_Tree:
    # コンストラクタ。リストもしくは要素数にて初期化。
    # デフォルトでは最小値を求めるが、op(operation=演算内容、デフォルトは最小値)、
    # ie(identity element単位元)を指定することも可能(f.e: op=operator.add, ie=0)
    def __init__(self, arg1, op=lambda x, y:x if x < y else y, ie=math.inf):
        self.op = op
        self.ie = ie

        if type(arg1) == int:
            default_list = []
            self.length = arg1
        else:
            default_list = list(arg1)
            self.length = len(arg1)

        # 全体の深さ、上位構造分のオフセットを求める
        self.depth = 0
        self.offset = 1
        while self.offset < self.length:
            self.depth += 1
            self.offset *= 2

        # 木の初期化。構造は1-indexedで使用していくことにする
        self.tree = [self.ie] * (self.offset * 2)
        if default_list:
            self.tree[self.offset:self.offset+self.length] = default_list
            self.refresh()

    # 全体の再計算(愚直に……)
    def refresh(self):
        for idx in range(self.offset - 1, 0, -1):
            self.tree[idx] = self.op(self.tree[idx*2], self.tree[idx*2+1])

    # 値のセット、及び関連する部分の再計算
    def set(self, idx, value):
        idx = idx + self.offset
        self.tree[idx] = value
        while idx > 1:
            idx //= 2
            old = self.tree[idx]
            new = self.op(self.tree[idx*2], self.tree[idx*2+1])
            if old == new:
                break
            else:
                self.tree[idx] = new
        
    # 半開区間[left, right)における欲しい値(アレっすよ、アレ)を求める
    def find(self, left, right):
        # 区間がおかしなときは、エラー代わりに単位元とかでも返しておく
        if left >= right:
            return self.ie
        
        # 左端と右端から上位を見ていく
        result = self.ie
        left = left + self.offset
        right = right + self.offset - 1

        # 左端と右端が重なるとこまで演算
        while left <= right:
            # 左端は、自身が親の右側の子の時(=ノード番号が奇数のとき)にだけ演算する
            if left % 2 == 1:
                result = self.op(result, self.tree[left])
            # 一段上に移動
            left = (left + 1) // 2

            # 右端は、自身が親の左側の(以下略
            if right % 2 == 0:
                result = self.op(result, self.tree[right])
            right = (right - 1) // 2
       
        return result
    
    # データ領域の値をindexに応じて返す
    def get(self, x):
        return self.tree[x+self.offset]

    # 全領域を対象にした計算値を返す
    def find_all(self):
        return self.tree[1]
    
    # 保持している値全体を返す（デバッグ用？）
    def show_tree(self):
        print(self.tree)

def main():
    N = int(input())
    h_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))

    dpt = Segment_Tree(N+1, op=lambda x,y:x if x>y else y, ie=0)

    for height, beauty in zip(h_list, b_list):
        max_to_left = dpt.find(0, height)
        dpt.set(height, max(dpt.get(height), max_to_left + beauty))
    
    print(dpt.find_all())

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# 演算内容、単位元の必要に応じて(コンストラクタ参照)
import math

# セグメント木のクラス
# 後日遅延評価なども取り入れていきたいが、とりあえず
# 基本的なところだけを分かりやすい形で組んでみたもの
# length:データ部の長さ depth:構造全体の深さ
# offset:上位構造の長さ tree:全体リスト

class Segment_Tree:
    # コンストラクタ。リストもしくは要素数にて初期化。
    # デフォルトでは最小値を求めるが、op(operation=演算内容、デフォルトは最小値)、
    # ie(identity element単位元)を指定することも可能(f.e: op=operator.add, ie=0)
    def __init__(self, arg1, op=lambda x, y:x if x < y else y, ie=math.inf):
        self.op = op
        self.ie = ie

        if type(arg1) == int:
            default_list = []
            self.length = arg1
        else:
            default_list = list(arg1)
            self.length = len(arg1)

        # 全体の深さ、上位構造分のオフセットを求める
        self.depth = 0
        self.offset = 1
        while self.offset < self.length:
            self.depth += 1
            self.offset *= 2

        # 木の初期化。構造は1-indexedで使用していくことにする
        self.tree = [self.ie] * (self.offset * 2)
        if default_list:
            self.tree[self.offset:self.offset+self.length] = default_list
            self.refresh()

    # 全体の再計算(愚直に……)
    def refresh(self):
        for idx in range(self.offset - 1, 0, -1):
            self.tree[idx] = self.op(self.tree[idx*2], self.tree[idx*2+1])

    # 値のセット、及び関連する部分の再計算
    def set(self, idx, value):
        idx = idx + self.offset
        self.tree[idx] = value
        while idx > 1:
            idx //= 2
            old = self.tree[idx]
            new = self.op(self.tree[idx*2], self.tree[idx*2+1])
            if old == new:
                break
            else:
                self.tree[idx] = new
        
    # 半開区間[left, right)における欲しい値(アレっすよ、アレ)を求める
    def find(self, left, right):
        # 区間がおかしなときは、エラー代わりに単位元でも返しておく
        if left >= right:
            return self.ie
        
        # 1(tree全体を含むもの)から探索開始。キューには探索対象の深さも一緒に入れておく
        result = self.ie
        queue = [(1, 0)]
        while len(queue) > 0:
            node, node_depth = queue.pop()

            # 対象ノードが受け持つ区間を求める
            width = 2 ** (self.depth - node_depth)
            idx_in_row = node - 2 ** (node_depth)
            node_left = width * idx_in_row
            node_right = node_left + width

            # 範囲外なら探索終了
            if node_right <= left or right <= node_left:
                continue

            # はみ出てたら子をキューに追加
            if node_left < left or right < node_right:
                queue.append((node * 2, node_depth + 1))
                queue.append((node * 2 + 1, node_depth + 1))
                continue

            # ここまで来たのならノードの情報は探索範囲に包含されている
            result = self.op(result, self.tree[node])
        
        return result
    
    def get(self, x):
        return self.tree[x+self.offset]

    def find_all(self):
        return self.tree[1]
    
    def show_tree(self):
        print(self.tree)


def main():
    N = int(input())
    dpt = Segment_Tree(N + 1, op=lambda x, y:x if x>y else y, ie=0)
    h_list = list(map(int, input().split()))
    a_list = list(map(int, input().split()))

    for height, beauty in zip(h_list, a_list):
        value = dpt.find(0, height) + beauty
        dpt.set(height, max(value, dpt.get(height)))
    
    print(dpt.find_all())

if __name__ == '__main__':
    main()