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

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
# 単位元とseg_funcを設定する
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() #n以上の最小の2のべき乗
        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 a+b #0
        #return a*b #1
        #return gcd(a,b) #0
        return max(a,b) #-1か-10**10 (十分小さいもの)
        #return min(a,b) #10**10 (十分大きいもの)
    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): #O(logN)
        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) #最後の高さがjの並べ方のうち最大の美しさ
    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()

Submission status: Accepted

Solution code:
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:  # [x, y)
        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))

Submission status: Accepted

Solution code:
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

    # SEG木は1-index
    # Aに関しては0-index

    def __init__(self, n):  # Aは0-idx
        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 delay(self,):

    def query(self, left, right):
        # maspy式。開区間のママ処理する
        # left, rightで値を分けているのは交換法則不成立のときのため
        # 開区間→Rが奇数→右端が偶数→1ずらしてから計算
        # 　下から上への遷移は2で割る
        # juppy氏は閉区間に直していた
        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)

Submission status: Accepted

Solution code:

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

    # dpをセグメントツリーで管理
    # dp[hi] = a[i] + max(dp[j]) for j < hi
    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()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
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()

Submission status: Accepted

Solution code:
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)
        #self._build(array)
    
    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()

Submission status: Accepted

Solution code:
class SegmentTree:  # 0-indexed
    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):  # [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))

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
#BIT

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

inf=float('inf')

#DP[height]=heightの時の最大美しさ
DP=[0]*(N+1)
#DPの最大値を求めるために使う
BIT=[0]*(N+1)

#DP[1]からDP[idx]までの最大値
def BIT_query(idx): #1<=idx
    global BIT

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

#DP[idx]がxに変化したときにBITを変化させる
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])
#print(DP,BIT)
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('i={0}'.format(i),DP,BIT)

print(BIT_query(N))

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
# dp[i][j]=(i番目まで使って最後の高さがjであるようなものの美しさの最大値)
# dp[i][j]=max(dp[i-1][k])+a[i](h[i]==j,0<=k<j),dp[i-1][j](otherwise)

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

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
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
    #LIS
    N=I()
    h=LI()
    a=LI()
    
    #####segfunc######

    #評価関数（という言い方であっている？）
    def segfunc(x,y):
        return max(x,y)


    #初期化
    def init(init_val):
        #init_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]) 
            

    #k番目の値をxに更新
    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])

            
    #[p,q)の区間に対するクエリへの応答
    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:N以上の最小の2のべき乗
    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()

Submission status: Accepted

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

#####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:
        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:n以上の最小の2のべき乗
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))

Submission status: Accepted

Solution code:
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)

#update(i,x):Aiをxに更新する
def update(i,x):
    k = i + num - 1
    while k >= 0:
        seg[k] = max(x,seg[k])
        k = (k-1)//2

#query(a,b,0,0,num):[a,b)の最大値
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))

Submission status: Accepted

Solution code:
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)

#update(i,x):Aiをxに更新する
def update(i,x):
    k = i + num - 1
    while k >= 0:
        seg[k] = max(x,seg[k])
        k = (k-1)//2

#query(a,b,0,0,num):[a,b)の最大値
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))

Submission status: Accepted

Solution code:
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)

#update(i,x):Aiをxに更新する
def update(i,x):
    k = i + num - 1
    while k >= 0:
        seg[k] = max(x,seg[k])
        k = (k-1)//2

#query(a,b,0,0,num):[a,b)の最大値
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))

Submission status: Accepted

Solution code:
n = int(input())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, i, x):
        self.b[i + self.n - 1] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r, i=0):
        j = i - (1 << ((i + 1).bit_length() - 1))+1
        length = 1 << (self.logn - (i + 1).bit_length() + 1)
        ll = j * length
        rr = (j + 1) * length
        if l <= ll and rr <= r:
            return self.b[i]
        elif rr <= l or r <= ll:
            return self.one
        else:
            return self.func(self.get_segment(l, r, i * 2 + 1),
                             self.get_segment(l, r, i * 2 + 2))


seg = SegmentTree([0]*(n+1))

for i in range(n):
    j = seg.get_segment(0, h[i] + 1)
    seg.update_func(h[i], j + a[i])
print(seg.get_segment(0, n+1))

Submission status: Accepted

Solution code:
n = int(input())
h = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]


class Bucket:
    def __init__(self, a, k, func=max, one=-10**18):
        self.n = len(a)
        self.k = k
        self.func = func
        self.one = one

        self.a = a[:]
        self.b = []
        for i in range(self.n // self.k):
            s = self.one
            for j in range(i * self.k, i * self.k + self.k):
                s = func(s, self.a[j])
            self.b.append(s)
        s = self.one
        for i in range(self.n // self.k * self.k, self.n):
            s = self.func(s, self.a[i])
        self.b.append(s)

    def get(self, index):
        s = self.one
        j = index // self.k
        for i in range(j):
            s = self.func(s, self.b[i])
        for i in range(j * self.k, index + 1):
            s = self.func(s, self.a[i])
        return s

    def update(self, index, x):
        self.a[index] = self.func(x, self.a[index])
        self.b[index//self.k] = self.func(self.b[index//self.k], x)


buc = Bucket([0] * (n+1), max(10, int(n**0.5)))

for i in range(n):
    j = buc.get(h[i])
    buc.update(h[i], j + a[i])

print(buc.get(n))

Submission status: Accepted

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/dp/tasks/dp_q
いわゆるインラインdpなのは分かった
→どこが？

dpを決めると、更新式がセグ木などで更新可能？
dp[i][h] = i番目まで見て、最大の高さがhの時の美しさの総和の最大値

dp[i][h] = max( dp[i-1][0] , dp[i-1][1] , … , dp[i-1][h-1] ) + a[i]
なので,RMQで処理できる
→これがインラインdpなのか？？

"""

def make_ST(n,first): #firstで初期化された、葉がn要素を超えるように2のべき乗個用意されたリストを返す

    i = 0
    ret = []
    while 2 ** (i-1) < n:

        for j in range(2 ** i):
            ret.append(first)

        i += 1

    return ret

def RMQ_update_point(num,point,tree): #葉のindex(0-origin)がpointの要素をnumにする/treeはセグ木

    i = (len(tree) - 1) // 2 + point
    tree[i] = num
    while i > 0:
        i = (i - 1) // 2
        tree[i] = max(tree[i * 2 + 2] , tree[i * 2 + 1])

    return

def RMQ_query(a,b,k,l,r,tree): #query区間左,右,注目ノード番号,担当範囲左,担当範囲右,木

    if r <= a or b <= l: #区間が完全にかぶらない場合inf
        return 0
    
    if a <= l and r <= b: #区間が完全に含まれる場合自分
        return tree[k]

    c1 = RMQ_query(a,b,2*k+1,l,(l+r)//2,tree)
    c2 = RMQ_query(a,b,2*k+2,(l+r)//2,r,tree)   

    return max(c1,c2)


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

tree = make_ST(N+1,0)

for i in range(N):

    maxi_sc = RMQ_query(0,h[i],0,0,(len(tree)+1)//2,tree)
    RMQ_update_point(maxi_sc+a[i] , h[i] ,tree)

print (RMQ_query(0,N+1,0,0,(len(tree)+1)//2,tree))

Submission status: Accepted

Solution code:
ide = 0
def func(a,b):
  return max(a,b)
class SegmentTree:
  def __init__(self,ls,commutative = True):
    if commutative == True:
      self.n = len(ls)
      self.tree = [ide for i in range(self.n)]+ls
    else:
      self.n = 2**((len(ls)-1).bit_length())
      self.tree = [ide for i in range(self.n)]+ls+[ide for i in range(self.n-len(ls))]
    for i in range(1,self.n)[::-1]:
      self.tree[i] = func(self.tree[i<<1|0],self.tree[i<<1|1])
  def getall(self):
    return self.tree[1]
  def get(self,l,r):
    lret = ide
    rret = ide
    l += self.n
    r += self.n
    while l < r:
      if l&1:
        lret = func(lret,self.tree[l])
        l += 1
      if r&1:
        rret = func(self.tree[r-1],rret)
      l >>= 1
      r >>= 1
    ret = func(lret,rret)
    return ret
  def update(self,i,x):
    i += self.n
    self.tree[i] = x
    while i > 1:
      i >>= 1
      self.tree[i] = func(self.tree[i<<1|0],self.tree[i<<1|1])

n = int(input())
h = list(map(int,input().split()))
b = list(map(int,input().split()))
dp = [0 for i in range(n+1)]
ST = SegmentTree(dp)
for i in range(1,n+1):
  hi = h[i-1]
  bi = b[i-1]
  x = ST.get(0,hi)
  ST.update(hi,x+bi)
print(ST.getall())

Submission status: Accepted

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

def main():
    N = int(input())
    
    h = map(int,input().split())
    a = map(int,input().split())
    
    def segfunc(x,y):
        return max(x,y)
        
    def init(init_val):
        for i in range(N+1):
            seg[i+num-1] = init_val[i]
        for i in range(num-2,-1,-1):
            seg[i] = max(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[2*k+1],seg[2*k+2])
            
    def query(p,q):
        if q <= p:
            return ide_ele
        p += num-1
        q += num-2
        ret = ide_ele
        while q-p>1:
            if p&1 == 0:
                ret = segfunc(ret,seg[p])
            if q&1 == 1:
                ret = segfunc(ret,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        ret = segfunc(segfunc(ret,seg[p]),seg[q])
        return ret
        
    ide_ele = 0
    num = 2**N.bit_length()
    seg = [ide_ele]*2*num

    dp = [0]*(N+1)
    
    for he,be in zip(h,a):
        tmp = query(0,he)+be
        if tmp > dp[he]:
            dp[he] = tmp
            update(he,tmp)
    
    print(query(0,N+1))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    
    h = map(int,input().split())
    a = map(int,input().split())
    
    def segfunc(x,y):
        return max(x,y)
    
    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1],seg[2*k+2])
            
    def query(p,q):
        if q <= p:
            return ide_ele
        p += num-1
        q += num-2
        ret = ide_ele
        while q-p>1:
            if p&1 == 0:
                ret = segfunc(ret,seg[p])
            if q&1 == 1:
                ret = segfunc(ret,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        ret = segfunc(segfunc(ret,seg[p]),seg[q])
        return ret
        
    ide_ele = 0
    num = 2**N.bit_length()
    seg = [ide_ele]*2*num

    
    dp = [0]*(N+1)
    
    for he,be in zip(h,a):
        tmp = query(0,he)+be
        if tmp > dp[he]:
            dp[he] = tmp
            update(he,tmp)
    
    print(query(0,N+1))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)

def main():
    N = int(input())
    
    h = map(int,input().split())
    a = map(int,input().split())
    
    def segfunc(x,y):
        return max(x,y)
    
    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[2*k+1],seg[2*k+2])
            
    def query(p,q):
        if q <= p:
            return ide_ele
        p += num-1
        q += num-2
        ret = ide_ele
        while q-p>1:
            if p&1 == 0:
                ret = segfunc(ret,seg[p])
            if q&1 == 1:
                ret = segfunc(ret,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        ret = segfunc(segfunc(ret,seg[p]),seg[q])
        return ret
        
    ide_ele = 0
    num = 2**N.bit_length()
    seg = [ide_ele]*2*num

    
    dp = [0]*(N+1)
    
    for he,be in zip(h,a):
        tmp = query(0,he)+be
        if tmp > dp[he]:
            dp[he] = tmp
            update(he,tmp)
    
    print(max(dp))

if __name__ == "__main__":
    main()