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:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class Seg():
    def __init__(self, na, default, func):
        if isinstance(na, list):
            n = len(na)
        else:
            n = na
        i = 1
        while 2**i <= n:
            i += 1
        self.D = default
        self.H = i
        self.N = 2**i
        if isinstance(na, list):
            self.A = [default] * (self.N) + na + [default] * (self.N-n)
            for i in range(self.N-1,0,-1):
                self.A[i] = func(self.A[i*2], self.A[i*2+1])
        else:
            self.A = [default] * (self.N*2)
        self.F = func

    def find(self, i):
        return self.A[i + self.N]

    def update(self, i, x):
        i += self.N
        self.A[i] = x
        while i > 1:
            i = i // 2
            self.A[i] = self.merge(self.A[i*2], self.A[i*2+1])

    def merge(self, a, b):
        return self.F(a, b)

    def total(self):
        return self.A[1]

    def query(self, a, b):
        A = self.A
        l = a + self.N
        r = b + self.N
        res = self.D
        while l < r:
            if l % 2 == 1:
                res = self.merge(res, A[l])
                l += 1
            if r % 2 == 1:
                r -= 1
                res = self.merge(res, A[r])
            l >>= 1
            r >>= 1

        return res


def main():
    n = I()
    h = LI()
    a = LI()

    def f(a,b):
        if a < b:
            return b
        return a

    seg = Seg(n+1,0,f)
    for b,c in zip(h,a):
        t = seg.query(0, b)
        seg.update(b, t + c)

    return seg.total()


print(main())

Submission status: Time Limit Exceeded

Solution code:
def solve(n, hhh, aaa):
    n2 = 1 << n.bit_length()
    offset = n2 - 1
    data = [0] * ((n2 << 1) - 1)

    def update(k, x):
        i = k + offset
        data[i] = max(data[i], x)
        while i:
            i = (i - 1) // 2
            data[i] = max(data[i], x)

    def get_max(a, b, i=0, l=0, r=n2):
        if b <= l or r <= a:
            return 0

        if a <= l and r <= b:
            return data[i]

        m = (l + r) // 2
        li = (i << 1) + 1
        return max(get_max(a, b, li, l, m), get_max(a, b, li + 1, m, r))

    srt = sorted((h, i) for i, h in enumerate(hhh))
    for h, i in srt:
        update(i, get_max(0, i) + aaa[i])

    return get_max(0, n2)


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
print(solve(n, hhh, aaa))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, n, sentinel=0):
        self.n = 1 << n.bit_length()
        self.offset = self.n - 1
        m = (self.n << 1) - 1
        self.data = [sentinel] * m
        self.sentinel = sentinel

    def update(self, k, x):
        i = k + self.offset
        self.data[i] = max(self.data[i], x)
        while i:
            i = (i - 1) // 2
            self.data[i] = max(self.data[i], x)

    def get_max(self, a, b, i=0, l=0, r=None):
        if r is None:
            r = self.n

        if b <= l or r <= a:
            return self.sentinel

        if a <= l and r <= b:
            return self.data[i]

        m = (l + r) // 2
        li = (i << 1) + 1
        return max(self.get_max(a, b, li, l, m), self.get_max(a, b, li + 1, m, r))


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
srt = sorted((h, i) for i, h in enumerate(hhh))
lst = SegmentTree(n, 0)

for h, i in srt:
    lst.update(i, lst.get_max(0, i) + aaa[i])
    # print(lst.data)
print(lst.get_max(0, lst.n))

Submission status: Time Limit Exceeded

Solution code:
class LazySegmentTree:
    """
    Range Max Query
    Node must be positive.
    """

    def __init__(self, n, sentinel=0):
        self.n = 1 << (n + 1).bit_length()
        m = (self.n << 1) - 1
        self.data = [sentinel] * m
        self.lazy = [sentinel] * m
        self.flag = [False] * m
        self.sentinel = sentinel

    def _eval(self, i, l, r):
        if self.flag[i]:
            self.data[i] = max(self.data[i], self.lazy[i])
            if r - l > 1:
                li = (i << 1) + 1
                self.lazy[li] = max(self.lazy[li], self.lazy[i])
                self.lazy[li + 1] = max(self.lazy[li + 1], self.lazy[i])
                self.flag[li] = self.flag[li + 1] = True
            self.flag[i] = False

    def update(self, a, b, x, i=0, l=0, r=None):
        if r is None:
            r = self.n

        if b <= l or r <= a:
            return

        self._eval(i, l, r)

        if a <= l and r <= b:
            self.lazy[i] = x
            self.flag[i] = True
            self._eval(i, l, r)
        else:
            m = (l + r) // 2
            li = (i << 1) + 1
            self.update(a, b, x, li, l, m)
            self.update(a, b, x, li + 1, m, r)
            self.data[i] = max(self.data[li:li + 2])

    def get_max(self, a, b, i=0, l=0, r=None):
        if r is None:
            r = self.n

        if b <= l or r <= a:
            return self.sentinel

        self._eval(i, l, r)

        if a <= l and r <= b:
            return self.data[i]

        m = (l + r) // 2
        li = (i << 1) + 1
        return max(self.get_max(a, b, li, l, m), self.get_max(a, b, li + 1, m, r))


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
srt = sorted((h, i) for i, h in enumerate(hhh))
lst = LazySegmentTree(n, 0)

for h, i in srt:
    lst.update(i, lst.n, lst.get_max(0, i) + aaa[i])
    # print(lst.data)
    # print(lst.lazy)
    # print(lst.flag)
print(lst.get_max(0, n))

Submission status: Time Limit Exceeded

Solution code:
class LazySegmentTree:
    """
    Range Max Query
    Node must be positive.
    """

    def __init__(self, n, sentinel=0):
        self.n = n
        self.n2 = 1 << (n + 1).bit_length()
        m = (self.n2 << 1) - 1
        self.data = [sentinel] * m
        self.lazy = [sentinel] * m
        self.flag = [False] * m
        self.sentinel = sentinel

    def _eval(self, i, l, r):
        if self.flag[i]:
            self.data[i] = max(self.data[i], self.lazy[i])
            if r - l > 1:
                li = (i << 1) + 1
                self.lazy[li] = max(self.lazy[li], self.lazy[i])
                self.lazy[li + 1] = max(self.lazy[li + 1], self.lazy[i])
                self.flag[li] = self.flag[li + 1] = True
            self.flag[i] = False

    def update(self, a, b, x, i=0, l=0, r=None):
        if r is None:
            r = self.n

        if b <= l or r <= a:
            return

        self._eval(i, l, r)

        if a <= l and r <= b:
            self.lazy[i] = x
            self.flag[i] = True
            self._eval(i, l, r)
        else:
            m = (l + r) // 2
            li = (i << 1) + 1
            self.update(a, b, x, li, l, m)
            self.update(a, b, x, li + 1, m, r)
            self.data[i] = max(self.data[li:li + 2])

    def get_max(self, a, b, i=0, l=0, r=None):
        if r is None:
            r = self.n

        if b <= l or r <= a:
            return self.sentinel

        self._eval(i, l, r)

        if a <= l and r <= b:
            return self.data[i]

        m = (l + r) // 2
        li = (i << 1) + 1
        return max(self.get_max(a, b, li, l, m), self.get_max(a, b, li + 1, m, r))


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
srt = sorted((h, i) for i, h in enumerate(hhh))
lst = LazySegmentTree(n, 0)

for h, i in srt:
    lst.update(i, lst.n2, lst.get_max(0, i) + aaa[i])
    # print(lst.data)
    # print(lst.lazy)
    # print(lst.flag)
print(lst.get_max(0, n))

Submission status: Time Limit Exceeded

Solution code:
class LazySegmentTree:
    """
    Range Max Query
    Node must be positive.
    """

    def __init__(self, n, sentinel=0):
        self.n = n
        m = 1 << ((n + 1).bit_length() + 1)
        self.data = [sentinel] * m
        self.lazy = [sentinel] * m
        self.flag = [False] * m
        self.sentinel = sentinel

    def _eval(self, i, l, r):
        if self.flag[i]:
            self.data[i] = max(self.data[i], self.lazy[i])
            if r - l > 1:
                li = (i << 1) + 1
                self.lazy[li] = max(self.lazy[li], self.lazy[i])
                self.lazy[li + 1] = max(self.lazy[li + 1], self.lazy[i])
                self.flag[li] = self.flag[li + 1] = True
            self.flag[i] = False

    def update(self, a, b, x, i=0, l=0, r=None):
        if r is None:
            r = self.n

        if b <= l or r <= a:
            return

        self._eval(i, l, r)

        if a <= l and r <= b:
            self.lazy[i] = x
            self.flag[i] = True
            self._eval(i, l, r)
        else:
            m = (l + r) // 2
            li = (i << 1) + 1
            self.update(a, b, x, li, l, m)
            self.update(a, b, x, li + 1, m, r)
            self.data[i] = max(self.data[li:li + 2])

    def get_max(self, a, b, i=0, l=0, r=None):
        if r is None:
            r = self.n

        if b <= l or r <= a:
            return self.sentinel

        self._eval(i, l, r)

        if a <= l and r <= b:
            return self.data[i]

        m = (l + r) // 2
        li = (i << 1) + 1
        return max(self.get_max(a, b, li, l, m), self.get_max(a, b, li + 1, m, r))


n = int(input())
hhh = list(map(int, input().split()))
aaa = list(map(int, input().split()))
srt = sorted((h, i) for i, h in enumerate(hhh))
lst = LazySegmentTree(n, 0)

for h, i in srt:
    lst.update(i, n, lst.get_max(0, i) + aaa[i])
    # print(lst.data)
    # print(lst.lazy)
    # print(lst.flag)
print(lst.get_max(0, n))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
*H, = map(int, input().split())
*A, = map(int, input().split())

N0 = 2**(N).bit_length()
INF = 2**31-1
data = [-INF]*(2*N0)
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
def query(l, r):
    L = l + N0; R = r + N0
    yield -INF
    while L < R:
        if R & 1:
            R -= 1
            yield data[R-1]

        if L & 1:
            yield data[L-1]
            L += 1
        L >>= 1; R >>= 1

*I, = range(N)
I.sort(key=lambda x: (H[x], x))
def solve():
    update(0, 0)
    yield 0
    for i in I:
        v = max(query(0, i+1)) + A[i]
        yield v
        update(i+1, v)
print(max(solve()))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
*H, = map(int, input().split())
*A, = map(int, input().split())

N0 = 2**(N).bit_length()
INF = 2**31-1
data = [-INF]*(2*N0)
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
def query(l, r):
    L = l + N0; R = r + N0
    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s


*I, = range(N)
I.sort(key=lambda x: (H[x], x))
def solve():
    update(0, 0)
    yield 0
    for i in I:
        v = query(0, i+1) + A[i]
        yield v
        update(i+1, v)
print(max(solve()))

Submission status: Accepted

Solution code:
# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb  # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None


    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

# ===============================================================================================
### START ITERATE RECURSION ###
from types import GeneratorType


def iterative(f, stack=[]):
    def wrapped_func(*args, **kwargs):
        if stack: return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
                continue
            stack.pop()
            if not stack: break
            to = stack[-1].send(to)
        return to

    return wrapped_func


#### END ITERATE RECURSION ####

# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input

def out(var): sys.stdout.write(str(var))  # for fast output, always take string

def lis(): return list(map(int, inp().split()))

def stringlis(): return list(map(str, inp().split()))

def sep(): return map(int, inp().split())

def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n

def nextline(): out("\n")  # as stdout.write always print sring.

def testcase(t):
    for p in range(t):
        solve()

def printlist(a):
    for p in range(0, len(a)):
        out(str(a[p]) + ' ')

#=========================================================================================

def solve():
    class SegmentTree:
        def __init__(self, data, default=0, func=max):
            """initialize the segment tree with data"""
            self._default = default
            self._func = func
            self._len = len(data)
            self._size = _size = 1 << (self._len - 1).bit_length()

            self.data = [default] * (_size) + data + [default] * (_size - self._len)
            for i in range(_size - 1, -1, -1):
                self.data[i] = func(self.data[2 * i], self.data[2 * i + 1])

        def __delitem__(self, idx):
            self[idx] = self._default

        def __getitem__(self, idx):
            return self.data[idx + self._size]

        def __setitem__(self, idx, value):
            idx += self._size
            self.data[idx] = value
            idx >>= 1
            while idx:
                self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
                idx >>= 1

        def __len__(self):
            return self._len

        def query(self, start, stop):
            """func of data[start, stop)"""
            start += self._size
            stop += self._size

            res_left = res_right = self._default
            while start < stop:
                if start & 1:
                    res_left = self._func(res_left, self.data[start])
                    start += 1
                if stop & 1:
                    stop -= 1
                    res_right = self._func(self.data[stop], res_right)
                start >>= 1
                stop >>= 1

            return self._func(res_left, res_right)

        def __repr__(self):
            return "SegmentTree({0})".format(self.data)


    n=int(inp())
    h=lis()
    b=lis()
    dp=[0]*(n+5)
    s=SegmentTree(dp,default=0,func=max)
    for i in range(n):
        dp[h[i]]=s.query(1,h[i])+b[i]
        s[h[i]]=dp[h[i]]
    #print(dp)
    print(max(dp))















solve()

Submission status: Accepted

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

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]



n = val()
h = li()
v = li()

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

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





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


ans = 0

root = build([0] * (n + 1), 0, n)
for i in range(n):
    curr = query(root, 0, h[i] - 1)
    ans = max(ans, curr + v[i])
    update(root, h[i], curr + v[i])

print(ans)

Submission status: Accepted

Solution code:
# by the authority of GOD     author: manhar singh sachdev #

import os,sys
from io import BytesIO, IOBase
from collections import deque

def update(seg_tree,val,update_val,x):
    curr = deque([(1,x,1)])
    while len(curr):
        y = curr.popleft()
        if y[0]<=val<=y[1]:
            seg_tree[y[2]] = max(seg_tree[y[2]],update_val)
            if y[0]!=y[1]:
                curr.append((y[0],(y[0]+y[1])//2,2*y[2]))
                curr.append(((y[0]+y[1])//2+1,y[1],2*y[2]+1))

def trav(seg_tree,val,x):
    curr = deque([(1,x,1)])
    ans = 0
    while len(curr):
        y = curr.popleft()
        if y[1]<val:
            ans = max(ans,seg_tree[y[2]])
        elif y[0]<=val<=y[1] and y[0]!=y[1]:
            curr.append((y[0],(y[0]+y[1])//2,2*y[2]))
            curr.append(((y[0]+y[1])//2+1,y[1],2*y[2]+1))
    return ans

def main():
    n = int(input())
    h = list(map(int,input().split()))
    a = list(map(int,input().split()))
    x = 1<<n.bit_length()
    seg_tree = [0]*(x<<1)
    fin = 0
    for i in range(n):
        k = trav(seg_tree,h[i],x)
        fin = max(fin,a[i]+k)
        update(seg_tree,h[i],a[i]+k,x)
    print(fin)

#Fast IO Region
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

if __name__ == '__main__':
    main()

Submission status: Accepted

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

from itertools import accumulate
from functools import lru_cache

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

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



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

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





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

    

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

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


ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
H = list(map(int, input().split()))
A = list(map(int, input().split()))
size = 2**N.bit_length()
seg = [0 for i in range(2*size + 1)]

def update(i, x):
  i += size
  seg[i] = x
  while 1 < i:
    i >>= 1
    seg[i] = max(seg[i<<1|0], seg[i<<1|1])

def query_(a, b, k, l, r):
  ret = 0

  a += size
  b += size
  while a < b:
    if b & 1:
      b -= 1
      ret = max(ret, seg[b])

    if a & 1:
      ret = max(ret, seg[a])
      a += 1

    a >>= 1
    b >>= 1

  return ret


def query(a, b):
  return query_(a, b, 1, 0, N)

for i in range(N):
  temp = query(0, H[i])
  update(H[i], temp+A[i])

print(query(0, N+1))

Submission status: Accepted

Solution code:
#####segfunc######                                                              
def segfunc(x,y):
    return max(x,y)

def init(init_val):
    #set_val                                                                    
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built                                                                      
    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+1:
        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
n=int(input())
num=2**(n-1).bit_length()
seg=[ide_ele]*2*num
h=list(map(int,input().split()))
a=list(map(int,input().split()))
dp=[0]*n
init(dp)
ans=0
for i in range(n):
    tmp=query(0,h[i])
    update(h[i]-1,tmp+a[i])

ans=query(0,n)
print(ans)

Submission status: Accepted

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 BIT:

	def __init__(self,size):
		self.N = size
		self.bit = [0] * (self.N+1)

	def getSum(self,i):
		s = 0
		while 0 < i:
			s += self.bit[i]
			i -= i & -i

		return s

	def getMax(self,i):
		s = 0
		while 0 < i:
			s = max(s, self.bit[i])
			i -= i & -i

		return s

	def add(self,i,val):
		while i <= self.N:
			# for range summary query
			# self.bit[i] += val
			# for range maximum query
			self.bit[i] = max( self.bit[i], val )
			i += i & -i

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 = BIT(N)
	for n in range(N):
		tree.add( H[n], tree.getMax(H[n]) + A[n] )

	lis = tree.getMax(N)

	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()