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):
class SegmentTree:
    def __init__(self, a, mode='min'):
        self.mode = mode
        if self.mode == 'min':
            self.padding = float('inf')
        elif mode == 'max':
            self.padding = -float('inf')
        elif mode == 'sum':
            self.padding = 0
        
        n = len(a)
        self.N = 2 ** (n-1).bit_length()
        self.data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-n)
        for i in range(2*self.N-2, 0, -2):
            self.data[(i-1)//2] = self._segfunc(*[self.data[i], self.data[i-1]])
    
    def _segfunc(self, *v_list):
        if self.mode == 'min':
            return min(v_list)
        elif self.mode == 'max':
            return max(v_list)
        elif self.mode == 'sum':
            return sum(v_list)
    
    def update(self, idx, x):
        idx = self.N - 1 + idx
        self.data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.data[idx] = self._segfunc(
                *[self.data[2*idx+1], self.data[2*idx+2]]
            )
    
    def search(self, i, j):
        
        idx1 = self.N-1+i
        idx2 = self.N-1+j-1
        result = self.padding
        while idx1 + 1 < idx2:
            if idx1&1 == 0: 
                result = self._segfunc(*[result, self.data[idx1]])
            if idx2&1 == 1: 
                result = self._segfunc(*[result, self.data[idx2]])
                idx2 -= 1
            
            idx1 //= 2
            idx2 = (idx2 - 1)//2
        
        if idx1 == idx2:
            result = self._segfunc(result, self.data[idx1])
        else: 
            result = self._segfunc(*[result, self.data[idx1], self.data[idx2]])
        
        return result


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

dp = [0] * (N+1)
st = SegmentTree(dp, mode='max')

ans = 0
for h, a in zip(H, A):
  M = st.search(0, h)
  st.update(h, M + a)

print(st.search(0, N+1))

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



def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])

def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res


ide_ele_max = 0



num_max = 2**(len(str(bin(n-1))) -2)
seg_max=[ide_ele_max]*2*num_max

for i in range(n):
    h_i = h[i]
    update_max( h_i-1, query_max(0,h_i) + a[i] )

print(query_max(0,n))

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

N, = map(int, input().split())
Hs = map(int, input().split())
As = map(int, input().split())
 
bit = Bit(N)
for h, a in zip(Hs, As):
    a0 = bit.sum(h)
    bit.add(h, a0+a)
print(bit.sum(N))

Solution (Python):
def init(init_val):
    for i in range(n):
        MI[i+num-1] = init_val[i]
        MA[i+num-1] = init_val[i]
    for i in range(num-2, -1, -1):
        MI[i] = min(MI[2*i+1], MI[2*i+2])
        MA[i] = max(MA[2*i+1], MA[2*i+2])


def update(k, x):
    k += num-1
    MI[k] = x
    MA[k] = x
    while k+1:
        k = (k-1)//2
        MI[k] = min(MI[k*2+1], MI[k*2+2])
        MA[k] = max(MA[k*2+1], MA[k*2+2])


def rangemin(p, q):
    if q <= p:
        return 1 << 100
    p += num-1
    q += num-2
    res = 1 << 100
    while q-p > 1:
        if p & 1 == 0:
            res = min(res, MI[p])
        if q & 1 == 1:
            res = min(res, MI[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res, MI[p])
    else:
        res = min(min(res, MI[p]), MI[q])
    return res


def rangemax(p, q):
    if q <= p:
        return -1
    p += num-1
    q += num-2
    res = -1
    while q-p > 1:
        if p & 1 == 0:
            res = max(res, MA[p])
        if q & 1 == 1:
            res = max(res, MA[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res, MA[p])
    else:
        res = max(max(res, MA[p]), MA[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)]

num = 2**(n).bit_length()
MI = [1 << 100]*2*num
MA = [-1]*2*num
init(dp)

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

print(rangemax(0, n+1))

Solution (Python):

import sys
INF = float("inf")
import math


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s = max(s, self.tree[i])
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] = max(self.tree[i], x)
            i += i & -i


def solve(N: int, h: "List[int]", a: "List[int]"):

    seg = Bit(N+1)

    for i in range(N):
        temp = a[i] + seg.sum(h[i])
        seg.add(h[i], temp)
    print(seg.sum(N+1))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    h = [int(next(tokens)) for _ in range(N)]  
    a = [int(next(tokens)) for _ in range(N)]  
    solve(N, h, a)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
INF = float("inf")
import math


class SegmentTree(object):
    

    def __init__(self, N):
        
        self.idelem = 0
        
        self.func = max

        self.N0 = 1
        while self.N0 < N:
            self.N0 *= 2
        self.tree = [self.idelem]*(2*self.N0)

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

    def query(self, l, r):
        l += self.N0-1
        r += self.N0-1
        s = self.idelem
        while l < r:
            if r % 2 == 0:
                r -= 1
                s = self.func(s, self.tree[r])

            if l % 2 == 0:
                s = self.func(s, self.tree[l])
                l += 1
            l //= 2
            r //= 2
        return s

    def __str__(self):
        return str(self.tree[self.N0-1:-1])


def solve(N: int, h: "List[int]", a: "List[int]"):

    seg = SegmentTree(N+1)

    for i in range(N):
        temp = a[i] + seg.query(0, h[i])
        seg.update(h[i], temp)
    print(seg.query(0, N+1))
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    h = [int(next(tokens)) for _ in range(N)]  
    a = [int(next(tokens)) for _ in range(N)]  
    solve(N, h, a)


if __name__ == '__main__':
    main()

Solution (Python):
class SegmentTree:
    """Segment Tree (Point Update & Range Query)

    Query
        1. update(i, val): update i-th value to val
        2. query(low, high): find f(value) in [low, high)

    Complexity
        time complexity: O(log n)
        space complexity: O(n)
    """

    def __init__(self, N, f, default):
        self.N = 1 << (N-1).bit_length()
        self.default = default
        self.f = f
        self.segtree = [self.default] * ((self.N << 1) - 1)

    @classmethod
    def create_from_array(cls, arr, f, default):
        N = len(arr)
        self = cls(N, f, default)
        for i in range(N):
            self.segtree[self.N - 1 + i] = arr[i]

        for i in reversed(range(self.N - 1)):
            self.segtree[i] = self.f(
                self.segtree[(i << 1) + 1], self.segtree[(i << 1) + 2])
        return self

    def update(self, i, val):
        i += self.N - 1
        self.segtree[i] = val
        while i > 0:
            i = (i - 1) >> 1
            self.segtree[i] = self.f(
                self.segtree[(i << 1) + 1], self.segtree[(i << 1) + 2])

    def __getitem__(self, k):
        return self.segtree[self.N - 1 + k]

    def query(self, low, high):
        
        low, high = low + self.N, high + self.N
        ret = self.default
        while low < high:
            if low & 1:
                ret = self.f(ret, self.segtree[low-1])
                low += 1
            if high & 1:
                high -= 1
                ret = self.f(ret, self.segtree[high-1])
            low, high = low >> 1, high >> 1
        return ret


def main():
    N = int(input())
    H = [int(x) for x in input().split()]
    A = [int(x) for x in input().split()]
    rmq = SegmentTree(N, max, 0)
    H_idx = [(h, i) for i, h in enumerate(H)]
    H_idx.sort()
    for _, idx in H_idx:
        rmq.update(idx, rmq.query(0, idx) + A[idx])
    print(rmq.query(0, N))


if __name__ == '__main__':
    main()

Solution (Python):
N = int(input())
H = [int(h) for h in input().split()]
A = [int(a) for a in input().split()]


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


    


    
def update(k, x):
    k += N-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = max(seg[2*k+1], seg[2*k+2])
        
def query(p, q):
    p += N-1
    q += N-2
    res = 0
    while q-p > 1:
        if p&1 == 0:
            res = max(res, seg[p])
        if q&1 == 1:
            res = max(res, seg[q])
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        res = max(res, seg[q])
    else:
        res = max(res, seg[p], seg[q])
    return res

dp = [0]*N
dp[0] = A[0]
update(H[0]-1, A[0])
for i in range(N-1):
    dp[i+1] = query(0, H[i+1])+A[i+1]
    update(H[i+1]-1, dp[i+1])
    
print(max(dp))

Solution (Python):
class SegmentTree():
    """一点更新、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する
    update: i番目をvalに変更する
    get_min: 区間[begin, end)の最小値を求める
    """
    def __init__(self, n):
        self.n = n
        self.INF = 0
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [self.INF] * (2*self.size - 1)

    def update(self, i, val):
        i += (self.size - 1)
        self.node[i] = val
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = max(self.node[2*i + 1], self.node[2*i + 2])

    def get_max(self, begin, end):
        begin += (self.size - 1)
        end += (self.size - 1)
        s = self.INF
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                s = max(s, self.node[end])
            if (begin - 1) & 1:
                s = max(s, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2
        return s

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

memo = {}
for i in range(n):
    memo[h[i]-1] = i
st = SegmentTree(n)

for i in range(n):
    ind = memo[i]
    st.update(ind, st.get_max(0, ind) + a[ind])
ans = 0
for i in range(n):
    ans = max(ans, st.get_max(i, i+1))
print(ans)

Solution (Python):
NN = 18
MA = [-1] * ((1<<NN+1)-1)
def update(a, x):
    i = (1<<NN) - 1 + a
    MA[i] = x
    while True:
        i = (i-1) // 2
        MA[i] = max(MA[2*i+1], MA[2*i+2])
        if i == 0:
            break

def rangemax(x):
    l = 0 + (1<<NN)
    r = x + (1<<NN)
    ma = 0
    while l < r:
        if l%2:
            ma = max(ma, MA[l-1])
            l += 1
        if r%2:
            r -= 1
            ma = max(ma, MA[r-1])
        l >>= 1
        r >>= 1
    return ma

N = int(input())
H = [int(a) for a in input().split()]
A = [int(a) for a in input().split()]

for i in range(N):
    update(H[i], rangemax(H[i]) + A[i])

print(rangemax(N+1))

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

base = 1
while base <= n:
    base *= 2
tree = [0] * (base * 2)
dp = [0] * (n + 1)

for flower in range(n):
    
    x = base + h[flower]
    best = 0
    while x > 1:
        if x % 2 == 1:
            best = max(best, tree[x - 1])
        x //= 2
    dp[h[flower]] = best + a[flower]
    i = base + h[flower]
    while i >= 1:
        tree[i] = max(tree[i], dp[h[flower]])
        i //= 2
print(max(dp))

Solution (Python):
class SegmentTree:
    def __init__(self, n):
        self.tree = [0] * (2 * n)
        self.n = n

    def modify(self, pos, val):
        tree = self.tree
        pos += self.n
        tree[pos] = val
        while pos > 1:
            tree[pos//2] = max(tree[pos], tree[pos ^ 1])
            pos //= 2

    def query(self, L, R):
        res = 0
        L += self.n
        R += self.n
        while L < R:
            if L % 2 == 1:
                res = max(res, self.tree[L])
                L += 1
            if R % 2 == 1:
                R -= 1
                res = max(res, self.tree[R])

            L //= 2
            R //= 2

        return res


def solve(n, heights, beauty):
    dp = SegmentTree(n+1)
    for h, b in zip(heights, beauty):
        _max = dp.query(0, h)
        dp.modify(h, _max + b)

    return dp.query(0, n+1)


def main():
    n = int(input())
    heights = [int(c) for c in input().split()]
    beauty = [int(c) for c in input().split()]
    ans = solve(n, heights, beauty)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
class SegmentTree:
    __slots__ = ('n', 'op', 'tree')

    def __init__(self, seq, op=max):
        self.n = len(seq)
        self.op = op
        self.tree = [-1] * (2 * self.n)

        for i in range(self.n):
            self.tree[i+self.n] = seq[i]

        for i in reversed(range(1, self.n)):
            self.tree[i] = op(self.tree[2*i], self.tree[2*i+1])

    def modify(self, pos, val):
        assert pos < self.n
        pos += self.n
        self.tree[pos] = val
        while pos > 1:
            self.tree[pos//2] = self.op(self.tree[pos], self.tree[pos ^ 1])
            pos //= 2

    def query(self, L, R):
        assert L <= R and L >= 0 and R <= self.n
        res = 0
        L += self.n
        R += self.n
        while L < R:
            if L % 2 == 1:
                res = self.op(res, self.tree[L])
                L += 1
            if R % 2 == 1:
                R -= 1
                res = self.op(res, self.tree[R])

            L //= 2
            R //= 2

        return res


def solve(n, heights, beauty):
    dp = SegmentTree([0] * (n+1), op=max)

    for pos, b in zip(heights, beauty):
        best = dp.query(0, pos)
        dp.modify(pos, best + b)

    return dp.query(0, n+1)


def main():
    n = int(input())
    heights = [int(c) for c in input().split()]
    beauty = [int(c) for c in input().split()]
    ans = solve(n, heights, beauty)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
class SegmentTree:
    __slots__ = ('n', 'op', 'tree')

    def __init__(self, seq, op=max):
        self.n = len(seq)
        self.op = op
        self.tree = [-1] * self.n + seq
        for i in reversed(range(1, self.n)):
            self.tree[i] = op(self.tree[2*i], self.tree[2*i+1])

    def modify(self, pos, val):
        assert pos < self.n
        pos += self.n
        self.tree[pos] = val
        while pos > 1:
            self.tree[pos//2] = self.op(self.tree[pos], self.tree[pos ^ 1])
            pos //= 2

    def query(self, L, R):
        assert L <= R and L >= 0 and R <= self.n
        res = 0
        L += self.n
        R += self.n
        while L < R:
            if L % 2 == 1:
                res = self.op(res, self.tree[L])
                L += 1
            if R % 2 == 1:
                R -= 1
                res = self.op(res, self.tree[R])

            L //= 2
            R //= 2

        return res


def solve(n, heights, beauty):
    dp = SegmentTree([0] * (n+1), op=max)
    query = dp.query
    modify = dp.modify

    for flower in range(n):
        pos = heights[flower]
        best = query(0, pos)
        modify(pos, best + beauty[flower])

    return dp.tree[1]


def main():
    n = int(input())
    heights = [int(c) for c in input().split()]
    beauty = [int(c) for c in input().split()]
    ans = solve(n, heights, beauty)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import operator


class SegmentTree:
    __slots__ = ('n', 'op', 'tree')

    def __init__(self, seq, op=operator.add):
        self.n = len(seq)
        self.op = op
        self.tree = [-1] * self.n + seq
        for i in reversed(range(1, self.n)):
            self.tree[i] = op(self.tree[2*i], self.tree[2*i+1])

    def modify(self, pos, val):
        assert pos < self.n
        pos += self.n
        self.tree[pos] = val
        while pos > 1:
            self.tree[pos//2] = self.op(self.tree[pos], self.tree[pos ^ 1])
            pos //= 2

    def query(self, L, R):
        assert L <= R and L >= 0 and R <= self.n
        res = 0
        L += self.n
        R += self.n
        while L < R:
            if L % 2 == 1:
                res = self.op(res, self.tree[L])
                L += 1
            if R % 2 == 1:
                R -= 1
                res = self.op(res, self.tree[R])

            L //= 2
            R //= 2

        return res


def solve(n, heights, beauty):
    dp = [0] * (n+1)
    st = SegmentTree(dp, op=max)

    for flower in range(n):
        pos = heights[flower]
        val = st.query(0, heights[flower]) + beauty[flower]
        st.modify(pos, val)

    return st.tree[1]


def main():
    n = int(input())
    heights = [int(c) for c in input().split()]
    beauty = [int(c) for c in input().split()]
    ans = solve(n, heights, beauty)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import operator


class SegmentTree:
    def __init__(self, seq, op=operator.add):
        self.n = len(seq)
        self.op = op
        self.tree = [-1] * self.n + seq
        for i in reversed(range(1, self.n)):
            self.tree[i] = op(self.tree[2*i], self.tree[2*i+1])

    def modify(self, pos, val):
        assert pos < self.n
        pos += self.n
        self.tree[pos] = val
        while pos > 1:
            self.tree[pos//2] = self.op(self.tree[pos], self.tree[pos ^ 1])
            pos //= 2

    def query(self, L, R):
        assert L <= R and L >= 0 and R <= self.n
        res = 0
        L += self.n
        R += self.n
        while L < R:
            if L % 2 == 1:
                res = self.op(res, self.tree[L])
                L += 1
            if R % 2 == 1:
                R -= 1
                res = self.op(res, self.tree[R])

            L //= 2
            R //= 2

        return res


def solve(n, heights, beauty):
    dp = [0] * (n+1)
    st = SegmentTree(dp, op=max)

    for flower in range(n):
        pos = heights[flower]
        val = st.query(0, heights[flower]) + beauty[flower]
        st.modify(pos, val)

    return st.tree[1]


def main():
    n = int(input())
    heights = [int(c) for c in input().split()]
    beauty = [int(c) for c in input().split()]
    ans = solve(n, heights, beauty)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import operator


class SegmentTree:
    def __init__(self, seq, op=operator.add):
        self.n = len(seq)
        self.op = op
        self.tree = [-1] * self.n + seq
        for i in reversed(range(1, self.n)):
            self.tree[i] = op(self.tree[2*i], self.tree[2*i+1])

    def modify(self, pos, val):
        assert pos < self.n
        pos += self.n
        self.tree[pos] = val
        while pos > 1:
            self.tree[pos//2] = self.op(self.tree[pos], self.tree[pos ^ 1])
            pos //= 2

    def query(self, L, R):
        assert L <= R and L >= 0 and R <= self.n
        res = 0
        L += self.n
        R += self.n
        while L < R:
            if L % 2 == 1:
                res = self.op(res, self.tree[L])
                L += 1
            if R % 2 == 1:
                R -= 1
                res = self.op(res, self.tree[R])

            L //= 2
            R //= 2

        return res


def solve(n, heights, beauty):
    st = SegmentTree([0] * (n+1), op = lambda x, y: max(x, y))

    for flower in range(n):
        st.modify(heights[flower], st.query(0, heights[flower] + 1) + beauty[flower])

    return st.tree[1]


def main():
    n = int(input())
    heights = [int(c) for c in input().split()]
    beauty = [int(c) for c in input().split()]
    ans = solve(n, heights, beauty)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
class SegTree():
    def __init__(self, N):
        
        self.N0 = 2**(N-1).bit_length()
        self.INF = 2**31-1
        self.seg_max = [-self.INF]*(2*self.N0)

    def update(self, index, value):
        index += self.N0 - 1
        self.seg_max[index] = value
        while index > 0:
            index = (index - 1) // 2
            self.seg_max[index] = max(self.seg_max[index * 2 + 1], self.seg_max[index * 2 + 2])

    def query(self, first, last):
        first += self.N0 - 1
        last += self.N0 - 1
        ret = -self.INF
        while first <= last:
            if not first & 1:
                ret = max(ret, self.seg_max[first])
            if last & 1:
                ret = max(ret, self.seg_max[last])
            first = first // 2
            last = last // 2 - 1
        return ret


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

rnk2idx = {}
for i in range(N):
    rnk2idx[h[i]] = i+1
segtree = SegTree(N+1)
for i in range(1, N+1):
    segtree.update(i, 0)
for i in range(1, N+1):
    idx = rnk2idx[i]
    segtree.update(idx, segtree.query(1, idx) + a[idx-1])

print(segtree.query(1, N))

Solution (Python):
import sys

n = int(input())
h_ls = [int(i) for i in sys.stdin.readline().split()]
a_ls = [int(i) for i in sys.stdin.readline().split()]

x = 1
while x <= n:
    x *= 2
tree = [0] * (2 * x)
INF = 10**18
memo_ls = [0 for i in range(n+1)]
def update(k, x):
    while k > 0:
        tree[k] = max(tree[k], x)
        k //= 2

def query(k):
    
    best = 0
    while k > 1:
        if k % 2 == 1:
            best = max(best, tree[k-1])
        k //= 2
    return best

for i, (h, a) in enumerate(zip(h_ls, a_ls)):
    best = query(h + x)
    memo_ls[h] = best + a
    update(h + x, best + a)
print(max(memo_ls))

Solution (Python):
n = int(input())
heights = [int(c) for c in input().split()]
beauty = [int(c) for c in input().split()]



base = 1
while base <= n:
    base *= 2

tree = [0] * (2 * base)

dp = [0] * (n+1)
for i in range(n):
    x = heights[i] + base
    best = 0
    while x > 1:
        if x % 2 == 1:
            best = max(best, tree[x-1])
        x //= 2

    dp[heights[i]] = best + beauty[i]

    j = base + heights[i]
    while j >= 1:
        tree[j] = max(tree[j], dp[heights[i]])
        j //= 2


    
    
    


ans = max(dp)
print(ans)

Solution (Python):

import sys
input = sys.stdin.readline


INF = (1 << 31) - 1

class SegmentTree:
    def __init__(self, N):
        self.N = 2**(N-1).bit_length()
        self.data = [[0, -1] for _ in range(2*self.N-1)]

    
    def get(self, k):
        k += self.N - 1
        s = self.data[k][0]
        while k > 0:
            k = (k-1)//2
            s = max(s, self.data[k][0])
        return s

    def update(self, l, x):
        L = l + self.N
        R = 2*self.N
        while L < R:
            if R & 1:
                R -= 1
                if x > self.data[R-1][0]:
                    self.data[R-1][0] = x
            if L & 1:
                if x > self.data[L-1][0]:
                    self.data[L-1][0] = x
                L += 1
            L >>= 1; R >>= 1

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

ST = SegmentTree(N+1)

ans = 0
for h, a in zip(H, A):
    m = ST.get(h)
    ans = max(ans, m+a)
    ST.update(h, m+a)

print(ans)

Solution (Python):
class SegmentTree:
  def __init__(self, size, default, op = max):
    self.size = 2**size.bit_length()
    self.dat = [default]*(self.size*2)
    self.op = op

  def update(self, i, x):
    i += self.size
    self.dat[i] = x
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i*2], self.dat[i*2+1])

  def add(self, i, x):
    i += self.size
    self.dat[i] = self.op(self.dat[i], x)
    while i > 0:
      i >>= 1
      self.dat[i] = self.op(self.dat[i], x)

  def get(self, a, b = None):
    if b is None:
      b = a + 1
    l, r = a + self.size, b + self.size
    res = None
    while l < r:
      if l & 1:
        if res is None:
          res = self.dat[l]
        else:
          res = self.op(res, self.dat[l])
        l += 1

      if r & 1:
        r -= 1
        if res is None:
          res = self.dat[r]
        else:
          res = self.op(res, self.dat[r])
      l >>= 1
      r >>= 1
    return res

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

dp = SegmentTree(N,0)
for i in range(N):
  h = H[i]
  a = A[i]
  dp.update(h-1,dp.get(0,h)+a)
print(dp.get(0,N))

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

class BitMax:
    def __init__(self, n):
        self.n = n + 3
        self.table = [0] * (self.n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            if x > self.table[i]: self.table[i] = x
            i += i & -i

    def max(self, i):
        i += 1
        res = 0
        while i > 0:
            if self.table[i] > res: res = self.table[i]
            i -= i & -i
        return res

def main():
    n = int(input())
    hh = LI()
    aa = LI()
    dp = BitMax(n + 1)
    for h, a in zip(hh, aa):
        dp.update(h, dp.max(h - 1) + a)
    print(dp.max(n))

main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

class BitMax:
    def __init__(self, n):
        self.n = n + 3
        self.table = [0] * (self.n + 1)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.table[i] = max(self.table[i], x)
            i += i & -i

    def max(self, i):
        i += 1
        res = 0
        while i > 0:
            res = max(res, self.table[i])
            i -= i & -i
        return res

def main():
    n=int(input())
    hh=LI()
    aa=LI()
    dp=BitMax(n+1)
    for h,a in zip(hh,aa):
        dp.update(h,dp.max(h-1)+a)
    print(dp.max(n))

main()

Solution (Python):




def SegmentTreeClosure(init_val, segfunc, ide_ele) -> 'update,query':
    size = 1 << (len(init_val) - 1).bit_length()

    
    tree = [ide_ele] * (size * 2 - 1)
    for idx, val in enumerate(init_val, size - 1):  
        
        tree[idx] = val
    for idx in range(size - 2, -1, -1):  
        tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

    
    def update(idx: int, val) -> None:
        nonlocal size
        nonlocal tree
        nonlocal segfunc

        idx += size - 1
        
        tree[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

    
    def query(left: int, right: int) -> 'result':
        nonlocal size
        nonlocal tree
        nonlocal segfunc

        left += size
        right += size
        ret = ide_ele  
        while left < right:  
            if left % 2:  
                ret = segfunc(ret, tree[left - 1])
                left += 1
            if right % 2:  
                right -= 1
                ret = segfunc(ret, tree[right - 1])
            left //= 2
            right //= 2

        return ret

    return update, query


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

dp = [0] * (n + 1)


update, query = SegmentTreeClosure(init_val=dp, segfunc=max, ide_ele=0)
for h_, a_ in zip(h, a):
    
    max_ = query(0, h_) + a_
    update(h_, max_)
print(query(0, n + 1))

Solution (Python):
mod = 10**9+7
class SegmentTree:
    def __init__(self, N, id, fun):
        self.N0 = 2**(N-1).bit_length()
        self.id = id
        self.data = [self.id]*(2*self.N0)
        self.fun = fun
    def update(self, k, x):
        k+=self.N0-1
        self.data[k] = x
        while k>=0:
            k = (k-1)//2
            self.data[k] = self.fun(self.data[2*k+1], self.data[2*k+2])
    def query(self, l, r):
        L = l+self.N0; R = r+self.N0
        s = self.id
        while L<R:
            if R&1:
                R-=1
                s = self.fun(s, self.data[R-1])
            if L&1:
                s = self.fun(s, self.data[L-1])
                L+=1
            L >>= 1; R>>=1
        return s
N = int(input())
h = list(map(int, input().split()))
a = list(map(int, input().split()))
R = SegmentTree(N+1, 0, max)
dp = [0]*N
dp[0] = a[0]
R.update(h[0], dp[0])
for i in range(1, N):
    m = R.query(0, h[i])
    dp[i] = m+a[i]
    R.update(h[i], dp[i])
print(max(dp))