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.

Solution (Python):



def update(tree, index, value):
    while index < len(tree):
        tree[index] = max(tree[index], value)
        index += index & -index


def read(tree, index):
    value = 0
    while index > 0:
        value = max(value, tree[index])
        index -= index & -index
    return value


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N = read_int()
    h = read_ints()
    a = read_ints()
    tree = [0]*(N+1)
    max_beauty = 0
    for i in range(N):
        beauty = read(tree, h[i])+a[i]
        update(tree, h[i], beauty)
        max_beauty = max(max_beauty, beauty)
    return max_beauty


if __name__ == '__main__':
    print(solve())

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
class SegTee:
    
    def __init__(self):
        self.arr=[0]*(4*n)
    def update(self,node,start,end,index,val):
        if index <start or index>end:
            return
        
        if start==end:
            
            
            self.arr[node]=val
        else:
            mid=(start+end)//2
            self.update(2*node+1,start,mid,index,val)
            self.update(2*node+2,mid+1,end,index,val)
            self.arr[node]=max(self.arr[2*node+1],self.arr[2*node+2])
            
    def query(self,node,tl,tr,l,r):
        if tl>r or tr<l:
            return 0
        elif tl>=l and tr<=r:
            return self.arr[node]
        else:    
            mid=(tr+tl)//2
            p1=self.query(2*node+1,tl,mid,l,r)
            p2=self.query(2*node+2,mid+1,tr,l,r)
            return max(p1,p2)
    

n = int(raw_input())
hi = list(map(int,raw_input().split()))
co= list(map(int,raw_input().split()))


segTree=SegTee()
dp=[0]*(n)
ans=0
for i in range(n):
  x=hi[i]
  y=segTree.query(0,0,n-1,0,x-1)
  dp[i]=y+co[i]
  ans=max(ans,dp[i])
  
  segTree.update(0,0,n-1,x-1,dp[i])
  

print(segTree.query(0,0,n-1,0,n-1))

Solution (Python):
class RMQ:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
    def max(self, i):
        s = 0
        while i > 0:
            if s < self.tree[i]:
                s = self.tree[i]
            i -= i & -i
        return s
    def __setitem__(self, i, x):
        while i <= self.size:
            if self.tree[i] < x:
                self.tree[i] = x
            i += i & -i


N, *HA = map(int, open(0).read().split())
H, A = HA[:N], HA[N:]

dp = RMQ(N)
for h, a in zip(H, A):
    dp[h] = a + dp.max(h)

print(dp.max(N))

Solution (Python):
class RMQ:
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
    def sum(self, i):
        s = 0
        while i > 0:
            if s < self.tree[i]:
                s = self.tree[i]
            i -= i & -i
        return s
    def add(self, i, x):
        while i <= self.size:
            if self.tree[i] < x:
                self.tree[i] = x
            i += i & -i


N, *HA = map(int, open(0).read().split())
H, A = HA[:N], HA[N:]

dp = RMQ(N)
for h, a in zip(H, A):
    dp.add(h, a + dp.sum(h))

print(dp.sum(N))

Solution (Python):
N=int(input())
H=tuple(map(int,input().split()))
A=tuple(map(int,input().split()))
class SegTreeMax:
    def __init__(self,N):
        self.N0=2**(N-1).bit_length()
        self.INF=2**63-1
        self.data=[-self.INF]*(2*self.N0)
        self.d=[0]*N
    def update(self,i,x):
        self.d[i]=x
        i+=self.N0-1
        self.data[i]=x
        while i>0:
            i=(i-1)//2
            self.data[i]=max(self.data[i*2+1],self.data[i*2+2])
    def max(self,l,r):
        L = self.N0 + l; R = self.N0 + r
        s = -self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = max(s, self.data[R-1])
            if L & 1:
                s = max(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
s=SegTreeMax(N+1)
s.update(0,0)
for i,h in enumerate(H):
    m=s.max(0,h)
    s.update(h,m+A[i])
print(s.max(0,N+1))

Solution (Python):
import sys
input = sys.stdin.readline

class RmaxQ:
    def __init__(self, original):
        self.n = len(original)
        self.INF = -(2**31)
        self.N0 = 1 << (self.n-1).bit_length()
        self.seg = [self.INF]*(self.N0 << 1)
        for i, j in enumerate(original, self.N0):
            self.seg[i] = j
        for i in range(self.N0-1, 0, -1):
            self.seg[i] = max(self.seg[2*i], self.seg[2*i+1])

    def get(self, i):
        return self.seg[i+self.N0]
        
    def update(self, i, x):
        i += self.N0
        self.seg[i] = x
        while i > 1:
            y = self.seg[i ^ 1]
            if y >= x:
                break
            i >>= 1
            self.seg[i] = x
                

    def add(self, i, d):
        self.update(i, self.get(i)+d)

    def query(self, l, r):
        res = self.INF
        l += self.N0
        r += self.N0
        while l < r:
            if r & 1:
                res = max(res, self.seg[r-1])
            if l & 1:
                res = max(res, self.seg[l])
                l += 1
            l >>= 1
            r >>= 1
     
        return res
        
n = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
dp = RmaxQ([0]*(n+1))
for i in range(n):
  h, a = H[i], A[i]
  dp.update(h, max(dp.get(h), dp.query(0, h)+a))
ans = dp.query(0, n+1)
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()

from fractions import gcd
class seg():
    def __init__(self,init_val):
        self.n=len(init_val)
        self.ide_ele=0 
        self.num=2**(self.n-1).bit_length() 
        self.seg=[self.ide_ele]*2*self.num
        for i in range(self.n):
            self.seg[i+self.num-1]=init_val[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i]=self.seg_func(self.seg[2*i+1],self.seg[2*i+2])
    def seg_func(self,a,b):
        
        
        
        return max(a,b) 
        
    def update(self,k,x):
        k+=self.num-1
        self.seg[k]=x
        while k:
            k=(k-1)//2
            self.seg[k]=self.seg_func(self.seg[k*2+1],self.seg[k*2+2])
    def query(self,p,q): 
        if q<=p:return self.ide_ele
        p+=self.num-1
        q+=self.num-2
        self.res=self.ide_ele
        while q-p>1:
            if p&1==0:
                self.res=self.seg_func(self.res,self.seg[p])
            if q&1==1:
                self.res=self.seg_func(self.res,self.seg[q])
                q-=1
            p=p//2
            q=(q-1)//2
        if p==q:self.res=self.seg_func(self.res,self.seg[p])
        else:self.res=self.seg_func(self.seg_func(self.res,self.seg[p]),self.seg[q])
        return self.res

def main():
    n=int(input())
    H=list(map(int,input().split()))
    A=list(map(int,input().split()))
    dp=[0]*(n+1) 
    seg_dp=seg(dp)
    for i in range(n):
        temp=seg_dp.query(1,H[i])
        seg_dp.update(H[i],temp+A[i])
    print(seg_dp.query(1,n+1))

if __name__=='__main__':
    main()

Solution (Python):
from math import ceil, log

n = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))


class SegmentTree(object):
    __slots__ = ["elem_size", "tree", "default", "op"]

    def __init__(self, a: list, default: int, op):
        real_size = len(a)
        self.elem_size = elem_size = 1 << ceil(log(real_size, 2))
        self.tree = tree = [default] * (elem_size * 2)
        tree[elem_size:elem_size + real_size] = a
        self.default = default
        self.op = op

        for i in range(elem_size - 1, 0, -1):
            tree[i] = op(tree[i << 1], tree[(i << 1) + 1])

    def get(self, x: int, y: int) -> int:  
        l, r = x + self.elem_size, y + self.elem_size
        tree, result, op = self.tree, self.default, self.op
        while l < r:
            if l & 1:
                result = op(tree[l], result)
                l += 1
            if r & 1:
                r -= 1
                result = op(tree[r], result)
            l, r = l >> 1, r >> 1

        return result

    def set(self, i: int, value: int) -> None:
        k = self.elem_size + i
        self.tree[k] = value
        self.update(k)

    def update(self, i: int) -> None:
        op, tree = self.op, self.tree
        while i > 1:
            i >>= 1
            tree[i] = op(tree[i << 1], tree[(i << 1) + 1])


dp = SegmentTree([0] * (n+1), 0, max)

for i in range(n):
    v = dp.get(0, h[i]) + a[i]
    if v > dp.get(h[i], h[i]+1):
        dp.set(h[i], v)

print(dp.get(0, n+1))

Solution (Python):
class SEGMENT_TREE:
    def __init__(self, N):
        """
        INPUT
        N: 配列のサイズ
        segment tree: 1-indexedで構築
        original array: 0-indexed
                 1
           2           3
         4    5     6     7
        8 9 10 11 12 13 14 15
        ---------------------
        0 1 2  3  4  5  6  7
        """
        self.N = N
        self.tree = [0] * (2 * N)  

    def init(self, arr):
        N = self.N
        for i in range(N):
            self.tree[N + i] = arr[i]
        for i in range(N - 1, 0, -1):
            self.tree[i] = max(
                self.tree[i * 2], self.tree[i * 2 + 1])  

    def update(self, p, value):
        """配列arr[p]をvalueに変更"""
        i = p + self.N
        self.tree[i] = value
        while i > 1:
            self.tree[i // 2] = max(self.tree[i], self.tree[i ^ 1])  
            i //= 2

    def query(self, l, r):
        """
        l, r: 0-indexed
        半開区間[l, r)から条件を満たす数を返す
        """
        N = self.N
        res = 0  
        l += N
        r += N
        while l < r:
            if (l & 1):
                res = max(res, self.tree[l])
                l += 1
            if (r & 1):
                r -= 1
                res = max(res, self.tree[r])
            l //= 2
            r //= 2
        return res


if __name__ == "__main__":
    N = int(input())
    H = list(map(int, input().split()))
    A = list(map(int, input().split()))
    seg = SEGMENT_TREE(N + 1)
    for h, a in zip(H, A):
        left = seg.query(0, h + 1)
        seg.update(h, left + a)
    print(seg.query(0, N+1))

Solution (Python):
import sys

input = sys.stdin.buffer.readline

n = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
P = []
for i in range(n):
    P.append((H[i], A[i], i))
P.sort()


class SegmentTree:
    ele = 0

    func = max

    
    

    def __init__(self, n):  
        self.n = n
        self.num = 2 ** ((self.n - 1).bit_length())
        self.SEG = [self.ele] * (2 * self.num)

    def search(self, idx):
        return self.SEG[idx + self.num]

    def initialize(self, A):
        for i in range(self.n):
            self.SEG[i + self.num] = A[i]
        for i in range(self.num - 1, 0, -1):
            self.SEG[i] = self.func(self.SEG[2 * i], self.SEG[2 * i + 1])

    def update(self, idx, val):
        idx += self.num
        self.SEG[idx] = val
        idx //= 2
        while idx:
            self.SEG[idx] = self.func(self.SEG[2 * idx], self.SEG[2 * idx + 1])
            idx //= 2

    

    def query(self, left, right):
        
        
        
        
        
        resleft = self.ele
        resright = self.ele
        left += self.num
        right += self.num
        while right - left > 0:
            if left % 2 == 1:
                resleft = self.func(resleft, self.SEG[left])
                left += 1
            if right % 2 == 1:
                right -= 1
                resright = self.func(resright, self.SEG[right])
            left //= 2
            right //= 2
        return self.func(resleft, resright)


ST = SegmentTree(n)
ans = 0
for h, a, i in P:
    h -= 1
    temp = ST.query(0, i) + a
    ST.update(i, temp)
    ans = max(temp, ans)
print(ans)

Solution (Python):

import math

class SegTreeMax:
    def __init__(self, n):
        m = 1
        while m < n:
            m *= 2
        self.n = m
        self.dat = [0] * (2 * self.n - 1)

    def update(self, k, x):
        k += self.n - 1 
        self.dat[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = max(
                self.dat[2 * k + 1],
                self.dat[2 * k + 2]
            )
    
    def query(self, a, b, k=0, l=0, r=None):
        if not r:
            r = self.n
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.dat[k]
        m = (l + r) // 2
        vl = self.query(a, b, k * 2 + 1, l, m)
        vr = self.query(a, b, k * 2 + 2, m, r)
        return max(vl, vr)


def submit():
    n = int(input())
    h = list(map(int, input().split()))
    a = list(map(int, input().split()))

    
    
    sgt = SegTreeMax(n)
    
    for i in range(n):
        d = sgt.query(0, h[i])
        if d > 0:
            sgt.update(h[i] - 1, a[i] + d)
        else:
            sgt.update(h[i] - 1, a[i])
    print(sgt.query(0, n))


if __name__ == "__main__":
    submit()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 
input = lambda:sys.stdin.readline().rstrip()

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

def resolve():
    n = int(input())
    H = list(map(int, input().split()))
    D = {v : i for i, v in enumerate(sorted(H))}
    for i in range(n):
        H[i] = D[H[i]]
    A = list(map(int, input().split()))

    tree = SegmentTree([0] * (n + 1), max, 0)
    res = 0
    for h, a in zip(H, A):
        score = tree.sum(0, h) + a
        tree.update(h, score)

    print(tree.sum(0, n))
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7


class SegmentTree():
    f = max
    unit = 0
   
    def __init__(self,array):
        self.N = len(array)
        self.tree = [self.unit] * (2*self.N)
        
    
    def _build(self,array):
        for i,x in enumerate(array,self.N):
            self.tree[i] = x
        for i in range(self.N - 1,0,-1):
            self.tree[i] = self.f(self.tree[i << 1],self.tree[i << 1|1])
    
    def update(self,k,x):
        k += self.N
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.f(self.tree[k << 1],self.tree[k << 1|1])
    
    def query(self,l,r):
        l += self.N
        r += self.N
        vl = self.unit
        vr = self.unit
        while l < r:
            if l&1: 
                vl = self.f(vl,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                vr = self.f(self.tree[r],vr)
            l >>= 1
            r >>= 1
        return self.f(vl,vr)
    
    def __str__(self):
        return '\n'.join(' '.join(str(v) for v in self.tree[1<<i:1<<(i + 1)]) for i in range((2*self.N).bit_length()))

def main():
    N = int(input())
    H = list(map(int,input().split()))
    A = list(map(int,input().split()))

    st = SegmentTree([0] * N)
    ans = 0
    for i in range(N):
        a = st.query(0,H[i] - 1)
        ans = max(ans,a + A[i])
        st.update(H[i] - 1,a + A[i])
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
class SegmentTree:  
    def __init__(self, array, operation=min, identity=10**30):
        self.identity = identity
        self.n = len(array)
        self.N = 1 << (self.n - 1).bit_length()
        self.tree = [self.identity] * 2 * self.N
        self.opr = operation
        for i in range(self.n):
            self.tree[i+self.N-1] = array[i]
        for i in range(self.N-2, -1, -1):
            self.tree[i] = self.opr(self.tree[2*i+1], self.tree[2*i+2])

    def value(self, k):
        return self.tree[k+self.N-1]

    def update(self, k, x):
        k += self.N-1
        self.tree[k] = x
        while k+1:
            k = (k-1)//2
            self.tree[k] = self.opr(self.tree[k*2+1], self.tree[k*2+2])

    def query(self, p, q):  
        if q <= p:
            print("Oops!  That was no valid number.  Try again...")
            exit()
        p += self.N-1
        q += self.N-2
        res = self.identity
        while q-p > 1:
            if p & 1 == 0:
                res = self.opr(res, self.tree[p])
            if q & 1 == 1:
                res = self.opr(res, self.tree[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.opr(res, self.tree[p])
        else:
            res = self.opr(self.opr(res, self.tree[p]), self.tree[q])
        return res


n = int(input())
h = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]

dp = [0 for _ in range(n+1)]

ST = SegmentTree(dp, max, -1)

for i in range(n):
    ST.update(h[i], a[i] + ST.query(0, h[i]))

print(ST.query(0, n+1))

Solution (Python):
n = int(input())
H = list(map(int,input().split()))
A = list(map(int,input().split()))

HA = list(zip(H,A,range(1,n+1)))
HA.sort()
bit = [0]*(n+1)

def update(val,idx):
    while idx < n+1:
        bit[idx] = max(bit[idx], val)
        idx += idx&(-idx)
    return

def get(idx):
    res = 0
    while idx > 0:
        res = max(res,bit[idx])
        idx -= idx&(-idx)
    return res

for h,a,i in HA:
    update(a + get(i),i)
print(max(bit))

Solution (Python):


N=int(input())
H=[0]+list(map(int,input().split()))
A=[0]+list(map(int,input().split()))

inf=float('inf')


DP=[0]*(N+1)

BIT=[0]*(N+1)


def BIT_query(idx): 
    global BIT

    res=0
    while idx>0:
        res=max(res,BIT[idx])
        idx-=idx&(-idx)
    return res


def BIT_update(idx,x):
    global BIT
    global N

    while idx<=N:
        BIT[idx]=max(BIT[idx],x)
        idx+=idx&(-idx)

DP[H[1]]=A[1]
BIT_update(H[1],A[1])

for i in range(2,N+1):
    rel=BIT_query(H[i]-1)+A[i]
    if rel>DP[H[i]]:
        DP[H[i]]=rel
        BIT_update(H[i],rel)
    

print(BIT_query(N))

Solution (Python):
class SegmentTree:
    def __init__(self, A, n=18, inf=10**20):
        l = len(A)
        self.size = n
        self.array = [inf]*(2**(n+1)-1)
        for i in range(l):
            self.array[i+2**n-1] = A[i]
        for i in range(2**n-2, -1, -1):
            self.array[i] = max(self.array[2*i+1], self.array[2*i+2])

    def _subquery(self, l, r, k, i, j):
        if j <= l or r <= i:
            return 0
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_max = self._subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_max = self._subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return max(l_max, r_max)

    def max(self, l, r):
        return self._subquery(l, r, 0, 0, 2**self.size)

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = c
        while tmp > 0:
            tmp = (tmp - 1) // 2
            l = self.array[2 * tmp + 1]
            r = self.array[2 * tmp + 2]
            self.array[tmp] = max(l, r)

n = int(input())
*H, = map(lambda x: int(x)-1, input().split())
*A, = map(int, input().split())
DP = SegmentTree([0]*n)
for i in range(n):
    tmp = DP.max(0, H[i])
    DP.update(H[i], tmp+A[i])
print(DP.max(0, n))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, k, x):
        k += self.N0 - 1
        
        self.data[k] = x
        
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left, right):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        
        
        while L < R:
            if L & 1:
                res = self.segfunc(res, self.data[L - 1])
                L += 1
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.data[R - 1])
            L >>= 1
            R >>= 1
        
        
        return res


def solve():
    N = int(rl())
    h = list(map(int, rl().split()))
    a = list(map(int, rl().split()))
    
    dp = [0] * (N + 1)
    seg_tree = SegmentTree(dp, max, 0)
    for i in range(N):
        hi = h[i]
        seg_tree.update(hi, seg_tree.query(0, hi) + a[i])
    ans = seg_tree.query(0, N + 2)
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):



def segfunc(x,y):
    return max(x,y)


def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


N=int(input())
h=list(map(int,input().split()))
a=list(map(int,input().split()))
n=N+1

ide_ele = 0 
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
dp=[0]*n
init(dp)
for i in range(N):
    
    
    update(h[i],query(0,h[i])+a[i])
print(query(0,n))

Solution (Python):



def segfunc(x,y):
    return max(x,y)


def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]    
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


N=int(input())
h=list(map(int,input().split()))
a=list(map(int,input().split()))
n=N+1

ide_ele = 0 
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
dp=[0]*n
init(dp)
for i in range(N):
    update(h[i],query(0,h[i])+a[i])
print(query(0,n))

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    
    N=I()
    h=LI()
    a=LI()
    
    

    
    def segfunc(x,y):
        return max(x,y)


    
    def init(init_val):
        
        for i in range(N):
            seg[i+num-1]=init_val[i]    
        
        for i in range(num-2,-1,-1) :
            seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
            

    
    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

            
    
    def query(p,q):
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[p])
        else:
            res = segfunc(segfunc(res,seg[p]),seg[q])
        return res


    
    ide_ele = 0

    
    num =2**(N-1).bit_length()
    seg=[ide_ele]*2*num
    
    ans=0
    for i in range(N):
        score=query(0,h[i]-1)+a[i]
        update(h[i]-1,score)
        ans=max(ans,score)
        
    print(ans)
    
    

main()

Solution (Python):
INF = 10 ** 9
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  copy import deepcopy
from bisect import bisect_left

class SegmentTree():

    def __init__(self,init_val,func,unit): 
        n = len(init_val)
        self.unit = unit 
        self.size = pow(2,n - 1).bit_length() 
        self.seg = [self.unit] * (2 * self.size) 
        self.f = func 
        
        for i in range(n):
            self.seg[i + self.size - 1] = init_val[i] 
        
        for i in range(self.size - 2,-1,-1):
            self.seg[i] = self.f(self.seg[2 * i + 1],self.seg[2 * i + 2])
    
    def update(self,k,x): 
        k += self.size - 1
        self.seg[k] = x
        while k:
            k = (k - 1)//2
            self.seg[k] = self.f(self.seg[2 * k + 1],self.seg[2 * k + 2])
    
    def query(self,p,q): 
        if q <= p:
            return self.unit

        p += self.size - 1 
        q += self.size - 2
        res = self.unit

        while q - p > 1:

            if (p&1) == 0:
                res = self.f(res,self.seg[p])

            if (q&1) == 1:
                res = self.f(res,self.seg[q])
                q -= 1

            p //= 2
            q = (q - 1)//2
        
        if p == q:
            res = self.f(res,self.seg[p])
        else:
            res = self.f(self.f(res,self.seg[p]),self.seg[q])
        
        return res


def main():
    n = int(input())
    H = list(map(int,input().split()))
    A = list(map(int,input().split()))
    
    dp = SegmentTree([0] * (n + 1),max,0)
    ans = 0
    for i in range(n):
        before_beaty = dp.query(0,H[i])
        if dp.query(H[i],H[i] + 1) < A[i] + before_beaty:
            dp.update(H[i],before_beaty + A[i])
            ans = max(ans,before_beaty + A[i])
    
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
n=int(input())
h=list(map(int,input().split()))
a=list(map(int,input().split()))


def segfunc(x,y):
    return max(x,y)

def init(init_val):
    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res


ide_ele =0


num =2**(n).bit_length()
seg=[ide_ele]*2*num

dp=[0 for i in range(0,n)]
dp[0]=a[0]
update(h[0],dp[0])

for i in range(1,n):
    dp[i]=a[i]+query(0,h[i])
    if dp[i]>query(h[i],h[i]+1):
        update(h[i],dp[i])

print(max(dp))

Solution (Python):
N = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))

num = 2**((N+1).bit_length())

seg = [0]*(2*num-1)


def update(i,x):
    k = i + num - 1
    while k >= 0:
        seg[k] = max(x,seg[k])
        k = (k-1)//2


def query(a,b,k,l,r):
    if r <= a or b <= l:
        return -1
    elif a <= l and r <= b:
        return seg[k]
    else:
        return max(query(a,b,2*k+1,l,(l+r)//2),query(a,b,2*k+2,(l+r)//2,r))


for i in range(N):
    update(h[i], query(0,h[i],0,0,num) + a[i])

print(max(seg))

Solution (Python):
N = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))

num = 2
while num <= N+1:
    num *= 2

seg = [0]*(2*num-1)


def update(i,x):
    k = i + num - 1
    while k >= 0:
        seg[k] = max(x,seg[k])
        k = (k-1)//2


def query(a,b,k,l,r):
    if r <= a or b <= l:
        return -1
    elif a <= l and r <= b:
        return seg[k]
    else:
        return max(query(a,b,2*k+1,l,(l+r)//2),query(a,b,2*k+2,(l+r)//2,r))


for i in range(N):
    update(h[i], query(0,h[i],0,0,num) + a[i])

print(max(seg))

Solution (Python):
N = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))

num = 2
while num <= N+1:
    num *= 2

seg = [0]*(2*num-1)


def update(i,x):
    k = i + num - 1
    while k >= 0:
        seg[k] = max(x,seg[k])
        k = (k-1)//2


def query(a,b,k,l,r):
    if r <= a or b <= l:
        return -float("inf")
    elif a <= l and r <= b:
        return seg[k]
    else:
        return max(query(a,b,2*k+1,l,(l+r)//2),query(a,b,2*k+2,(l+r)//2,r))


for i in range(N):
    update(h[i], query(0,h[i],0,0,num) + a[i])

print(max(seg))