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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class SegTree():
    def __init__(self, N):
        # 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))

Submission status: Accepted

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

Submission status: Accepted

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


    # for j in range(i):
    #     if heights[i] > heights[j] and beauty[i] + dp[j] > max_beauty:
    #         max_beauty = beauty[i] + dp[j]


ans = max(dp)
print(ans)

Submission status: Accepted

Solution code:
# SegmantTreeの実装
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)]

    # k番目の値をget
    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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
mod = 10**9+7
class RMQ:
    def __init__(self, N):
        self.N0 = 2**(N-1).bit_length()
        self.INF = float('inf')
        self.data = [self.INF]*(2*self.N0)
    def update(self, k, x):
        k+=self.N0-1
        self.data[k] = x
        while k>=0:
            k = (k-1)//2
            self.data[k] = min(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.INF
        while L<R:
            if R&1:
                R-=1
                s = min(s, self.data[R-1])
            if L&1:
                s = min(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 = RMQ(N+1)
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])
    if m == -float('inf'):
        m = 0
    dp[i] = m+a[i]
    R.update(h[i], -dp[i])
print(max(dp))

Submission status: Accepted

Solution code:
# seg = SegmentTree(init_val=dp, segfunc=max, ide_ele=0)
class SegmentTree:
    # original: @solzard_
    def __init__(self,
                 init_val: 'initial value: iterable',
                 segfunc: 'operation unique in case',
                 ide_ele: 'identity element corresponding init_val' = 0,
                 ):
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.size = 1 << (len(init_val) - 1).bit_length()
        self.tree = self._build(init_val)

    def _build(self, init_val) -> 'tree':
        segfunc = self.segfunc

        tree = [self.ide_ele] * (self.size * 2 - 1)

        for idx, val in enumerate(init_val, self.size - 1):  # set
            # modify val if needed (e.g. str -> ord())
            tree[idx] = val

        for idx in range(self.size - 2, -1, -1):  # build
            tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

        return tree

    def update(self, idx: int, val) -> None:
        tree = self.tree
        segfunc = self.segfunc

        idx += self.size - 1
        # modify val if needed as same as in _build()
        tree[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            tree[idx] = segfunc(tree[idx * 2 + 1], tree[idx * 2 + 2])

    def query(self, left: int, right: int) -> 'result':
        left += self.size
        right += self.size
        ret = self.ide_ele  # left >= right: return self.ide_ele
        segfunc = self.segfunc
        tree = self.tree
        while left < right:
            if left & 1:  # odd
                ret = segfunc(ret, tree[left - 1])
                left += 1
            if right & 1:  # odd
                right -= 1
                ret = segfunc(ret, tree[right - 1])
            left >>= 1
            right >>= 1
        return ret


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

dp = [0] * (n + 1)
# dp[j] := 末尾jの単調増加列の美しさの総和の最大値

seg = SegmentTree(init_val=dp, segfunc=max, ide_ele=0)

for h_, a_ in zip(h, a):
    # i本目を取って末尾にするとき
    max_ = seg.query(0, h_) + a_
    seg.update(h_, max_)
print(seg.query(0, n + 1))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, a: list, e: 'default' = 0, f: 'function' = max):
        size = len(a)
        n = 1 << (size - 1).bit_length()
        seg = [e] * (n * 2 - 1)
        for i, a_ in enumerate(a, n - 1):
            seg[i] = a_
        for i in range(n - 2, -1, -1):
            seg[i] = f(seg[i * 2 + 1], seg[i * 2 + 2])
        self.size = size
        self.n = n
        self.seg = seg
        self.a = a
        self.e = e
        self.f = f

    def update(self, k, x):
        n = self.n
        seg = self.seg
        f = self.f

        k += n - 1
        seg[k] = x
        while k > 0:
            k = (k - 1) // 2
            seg[k] = f(seg[k * 2 + 1], seg[k * 2 + 2])

    def query(self, a, b, k=0, l=0, r=-1):
        if r < 0:
            r = self.n
        if r <= a or b <= l:
            return self.e
        if a <= l and r <= b:
            return self.seg[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 self.f(vl, vr)


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

dp = [0] * (n + 1)
# dp[j] := 末尾jの単調増加列の美しさの総和の最大値

seg = SegmentTree(a=dp, e=0, f=max)

for h_, a_ in zip(h, a):
    # i本目を取って末尾にするとき
    max_ = seg.query(0, h_) + a_
    seg.update(h_, max_)
print(seg.query(0, n + 1))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, a: list, e: 'default', f: 'function'):
        n = len(a)
        size = 1 << (n - 1).bit_length()  # 元の配列サイズ以上の最小の二冪 == 最下段
        v = [e] * (size * 2 - 1)
        for i in range(n):
            # size-1個の上段の次、size個目からn個が元の配列の代入位置
            v[size - 1 + i] = a[i]
        for i in range(size - 2, -1, -1):
            v[i] = f(v[i * 2 + 1], v[i * 2 + 2])

        self.n = n  # 元の配列の長さ
        self.size = size  # 元の配列サイズ以上の最小の二冪 == 最下段の要素数
        self.v = v  # Segtreeの配列
        self.e = e  # 初期値
        self.f = f  # 比較関数

    def update(self, k: 'index', x: 'val'):
        k += self.size - 1  # 最下段のindexに変更する
        self.v[k] = x  # 値を更新する
        while k > 0:
            k = (k - 1) // 2  # 親のindex
            self.v[k] = self.f(self.v[k * 2 + 1], self.v[k * 2 + 2])

    def get(self, a, b, k=0, l=0, r=-1):
        # [a,b)区間の処理結果を返す
        # 注目区間[l,r)
        if r < 0:
            r = self.size

        if r <= a or b <= l:
            return self.e
        # 区間が重ならない

        if a <= l and r <= b:
            return self.v[k]
        # 完全被覆

        m = (l + r) // 2
        return self.f(self.get(a, b, k * 2 + 1, l, m), self.get(a, b, k * 2 + 2, m, r))
        # 部分被覆


def solve(n, h, a):
    seg = SegmentTree([0] * (n + 1), 0, max)
    for i in range(n):
        seg.update(h[i], seg.get(0, h[i]) + a[i])
        # 1回あたり更新するのは1箇所だから、iを状態にもつ必要はなくて、配列を使い回すことができる
        # 区間maxが高速に計算できればいいから、セグメント木を使えばできる
    return seg.get(0, n + 1)


if __name__ == '__main__':
    import sys

    input = sys.stdin.readline

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

# https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035
# classやめた方が遅かった
# 比較関数minがグローバルにあるから、遅くなっていた？

Submission status: Accepted

Solution code:
def solve(n, h, a):
    size = 1 << ((n + 1) - 1).bit_length()  # 元の配列サイズ以上の最小の二冪 == 最下段
    # 高さに対する美しさの最大値なので、高さ[0,n]の(n+1)要素に対して、segを考える
    seg = [0] * (size * 2 - 1)

    def update(seg, k, x):
        k += size - 1
        seg[k] = x  # 値を更新する
        while k > 0:
            k = (k - 1) // 2  # 親のindex
            seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2])

    def get(seg, a, b, k=0, l=0, r=-1):
        # [a,b)区間の処理結果を返す
        # 注目区間[l,r)
        if r < 0:
            r = size

        if r <= a or b <= l:
            return 0
        # 区間が重ならない

        if a <= l and r <= b:
            return seg[k]
        # 完全被覆

        m = (l + r) // 2
        return max(get(seg, a, b, k * 2 + 1, l, m), get(seg, a, b, k * 2 + 2, m, r))
        # 部分被覆

    for h_, a_ in zip(h, a):
        update(seg, h_, get(seg, 0, h_) + a_)
        # 1回あたり更新するのは1箇所だから、iを状態にもつ必要はなくて、配列を使い回すことができる
        # 区間maxが高速に計算できればいいから、セグメント木を使えばできる
    return get(seg, 0, n + 1)


if __name__ == '__main__':
    import sys

    input = sys.stdin.readline

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

# https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, a: list, e: 'default', f: 'function'):
        n = len(a)
        size = 1 << (n - 1).bit_length()  # 元の配列サイズ以上の最小の二冪 == 最下段
        v = [e] * (size * 2 - 1)
        for i in range(n):
            # size-1個の上段の次、size個目からn個が元の配列の代入位置
            v[size - 1 + i] = a[i]
        for i in range(size - 2, -1, -1):
            v[i] = f(v[i * 2 + 1], v[i * 2 + 2])

        self.n = n  # 元の配列の長さ
        self.size = size  # 元の配列サイズ以上の最小の二冪 == 最下段の要素数
        self.v = v  # Segtreeの配列
        self.e = e  # 初期値
        self.f = f  # 比較関数

    def update(self, k: 'index', x: 'val'):
        k += self.size - 1  # 最下段のindexに変更する
        self.v[k] = x  # 値を更新する
        while k > 0:
            k = (k - 1) // 2  # 親のindex
            self.v[k] = self.f(self.v[k * 2 + 1], self.v[k * 2 + 2])

    def get(self, a, b, k=0, l=0, r=-1):
        # [a,b)区間の処理結果を返す
        # 注目区間[l,r)
        if r < 0:
            r = self.size

        if r <= a or b <= l:
            return self.e
        # 区間が重ならない

        if a <= l and r <= b:
            return self.v[k]
        # 完全被覆

        m = (l + r) // 2
        vl = self.get(a, b, k * 2 + 1, l, m)
        vr = self.get(a, b, k * 2 + 2, m, r)
        return self.f(vl, vr)
        # 部分被覆


def solve(n, h, a):
    seg = SegmentTree([0] * (n + 1), 0, max)
    for i in range(n):
        tmp = seg.get(0, h[i])
        seg.update(h[i], tmp + a[i])
        # 1回あたり更新するのは1箇所だから、iを状態にもつ必要はなくて、配列を使い回すことができる
        # 区間maxが高速に計算できればいいから、セグメント木を使えばできる
    return seg.get(0, n + 1)


if __name__ == '__main__':
    import sys

    input = sys.stdin.readline

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

# https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, a: list, e: 'default', f: 'function'):
        n = len(a)
        size = 1 << (n - 1).bit_length()  # 元の配列サイズ以上の最小の二冪 == 最下段
        v = [e] * (size * 2 - 1)
        for i in range(n):
            # size-1個の上段の次、size個目からn個が元の配列の代入位置
            v[size - 1 + i] = a[i]
        for i in range(size - 2, -1, -1):
            v[i] = f(v[i * 2 + 1], v[i * 2 + 2])

        self.n = n  # 元の配列の長さ
        self.size = size  # 元の配列サイズ以上の最小の二冪 == 最下段の要素数
        self.v = v  # Segtreeの配列
        self.e = e  # 初期値
        self.f = f  # 比較関数

    def update(self, k: 'index', x: 'val'):
        k += self.size - 1  # 最下段のindexに変更する
        self.v[k] = x  # 値を更新する
        while k > 0:
            k = (k - 1) // 2  # 親のindex
            self.v[k] = self.f(self.v[k * 2 + 1], self.v[k * 2 + 2])

    def get(self, a, b, k=0, l=0, r=-1):
        # [a,b)区間の処理結果を返す
        # 注目区間[l,r)
        if r < 0:
            r = self.size

        if r <= a or b <= l:
            return self.e
        # 区間が重ならない

        if a <= l and r <= b:
            return self.v[k]
        # 完全被覆

        m = (l + r) // 2
        vl = self.get(a, b, k * 2 + 1, l, m)
        vr = self.get(a, b, k * 2 + 2, m, r)
        return self.f(vl, vr)
        # 部分被覆


def solve(n, h, a):
    seg = SegmentTree([0] * (n + 1), 0, max)
    for i in range(n):
        tmp = seg.get(0, h[i])
        seg.update(h[i], tmp + a[i])
        # 1回あたり更新するのは1箇所だから、iを状態にもつ必要はなくて、配列を使い回すことができる
        # 区間maxが高速に計算できればいいから、セグメント木を使えばできる
    return seg.get(0, n + 1)


if __name__ == '__main__':
    n = int(input())
    h = tuple(map(int, input().split()))
    a = tuple(map(int, input().split()))
    print(solve(n, h, a))

# https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

"""
・最後の高さ -> 価値の総和
・BITでmaxを管理
"""

class BIT():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def get_max(self,i):
        s = 0
        while i:
            t = self.tree[i]
            if s<t:
                s=t
            i -= i & -i
        return s
 
    def update(self, i, x):
        while i < self.size:
            if self.tree[i] >= x:
                return
            self.tree[i] = x
            i += i & -i

bit = BIT(N)

for i,(a,h) in enumerate(zip(A,H),1):
    x = bit.get_max(h)
    bit.update(h,x+a)

answer = bit.get_max(N)
print(answer)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

"""
・最後の高さ -> 価値の総和
・BITでmaxを管理
"""

class BIT():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def get_max(self,i):
        s = 0
        while i:
            t = self.tree[i]
            if s<t:
                s=t
            i -= i & -i
        return s
 
    def update(self, i, x):
        while i < self.size:
            if self.tree[i] < x:
                self.tree[i] = x
            i += i & -i

bit = BIT(N)

for i,(a,h) in enumerate(zip(A,H),1):
    x = bit.get_max(h)
    bit.update(h,x+a)

answer = bit.get_max(N)
print(answer)

Submission status: Accepted

Solution code:
n = int(input())
num = [ int(v) for v in input().split() ]
beauty = [ int(v) for v in input().split() ]
ln = len(bin(n-1))-1
ln2 = 2**(ln-1)
segtree = [ 0 for i in range(2**ln-1) ]


def update(p, q=1):
    p += 2**(ln-1)-2
    r = 0
    while p >= 0:
        if r == 0:
            segtree[p] = q
            r = 1
        else:
            segtree[p] = max(segtree[p], q)
        p = (p-1)//2

def getmax(a,b,k=0,l=0,r=ln2):
    if r <= a or b <= l:
        return 0
    elif l == r:
        return 0
    elif a == l and b == r:
        return segtree[k]
    elif l + 1 == r:
        return segtree[k]
    else:
        return max( getmax(a,min(b,(l+r)//2),2*k+1,l,(l+r)//2), getmax(max(a,(l+r)//2),b,2*k+2,(l+r)//2,r) )

for i in range(n):
    a, b = num[i], beauty[i]
    c = getmax(0,a-1)
    update(a,b+c)
print(getmax(0,n))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class BIT(object):
    def __init__(self,A,dot,e,inv=None):
        n=len(A)
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__inv=inv
        self.__node=['$']+A # 1-indexed
        for i in range(1,n+1):
            j=i+(i&-i)
            if(j<=n): self.__node[j]=dot(self.__node[i],self.__node[j])

    def add(self,i,w):
        i+=1
        while(i<=self.__n):
            self.__node[i]=self.__dot(self.__node[i],w)
            i+=i&-i

    def sum(self,i):
        res=self.__e
        while(i>0):
            res=self.__dot(res,self.__node[i])
            i-=i&-i
        return res
def resolve():
    n=int(input())
    H=list(map(lambda x:int(x)-1,input().split()))
    A=list(map(int,input().split()))
    bit=BIT([0]*n,max,0)
    for i in range(n):
        bit.add(H[i],bit.sum(H[i])+A[i])
    print(bit.sum(n))
resolve()

Submission status: Accepted

Solution code:
n=int(input())
def f(x):
    s=0
    while x>0:
        s=max(s,t[x])
        x-=x&-x
    return s
def g(x,y):
    while x<n+1:
        t[x]=max(y,t[x])
        x+=x&-x
t=[0]*(n+1)
h=list(map(int,input().split()))
a=list(map(int,input().split()))
for i in range(n):
    g(h[i],f(h[i]-1)+a[i])
print(max(t))

Submission status: Accepted

Solution code:
# from https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_2
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
        while i>=0:
            if data[i]<x:
                data[i]=x
            else:
                break
            i=(i-1)//2

    def get_max(k):
        i=k+offset
        ret=data[i]
        while i:
            if i%2==0:
                ret=max(ret,data[i-1])
            i=(i-1)//2
        return ret

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

    return data[0]



n=int(input())
hhh=[int(i) for i in input().split()]
aaa=[int(i) for i in input().split()]
print(solve(n,hhh,aaa))