Buggy python submission (verdict: Time Limit Exceeded):


class SegmentTree:

    def __init__(self, array, aggregator):
        self.array = array
        self.aggregator = aggregator
        N = 1
        while N < len(array):
            N *= 2
        self.tree = [0]*(2*N-1)
        self.construct_tree(0, len(array)-1, 0)

    def construct_tree(self, low, high, pos):
        if low == high:
            self.tree[pos] = self.array[low]
        else:
            mid = (low+high)//2
            self.construct_tree(low, mid, 2*pos+1)
            self.construct_tree(mid+1, high, 2*pos+2)
            self.tree[pos] = self.aggregator(self.tree[2*pos+1],
                                             self.tree[2*pos+2])

    def query(self, qlow, qhigh):
        return self._query(qlow, qhigh, 0, len(self.array)-1, 0)

    def _query(self, qlow, qhigh, low, high, pos):
        if qlow <= low and high <= qhigh:
            return self.tree[pos]
        if qlow > high or qhigh < low:
            return 0
        mid = (low+high)//2
        return self.aggregator(self._query(qlow, qhigh, low, mid, 2*pos+1),
                               self._query(qlow, qhigh, mid+1, high, 2*pos+2))


    def update(self, index, value):
        self._update(index, value, 0, len(self.array)-1, 0)

    def _update(self, index, value, low, high, pos):
        if index < low or index > high:
            return
        if low == high:
            self.tree[pos] = value
        else:
            mid = (low+high)//2
            self._update(index, value, low, mid, 2*pos+1)
            self._update(index, value, mid+1, high, 2*pos+2)
            self.tree[pos] = self.aggregator(self.tree[2*pos+1], self.tree[2*pos+2])

    def __str__(self):
        start, end = 0, 1
        levels = []
        while end-1 <= len(self.tree):
            levels.append(self.tree[start:end])
            start, end = end, end+(end-start)*2
        return '\n'.join(map(str, levels))


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


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


def solve():
    N = read_int()
    h = read_ints()
    a = read_ints()
    segment_tree = SegmentTree([0]*(N+1), max)
    max_beauty = 0
    for i in range(N):
        beauty = segment_tree.query(0, h[i]-1)+a[i]
        segment_tree.update(h[i], beauty)
        max_beauty = max(max_beauty, beauty)
    return max_beauty


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


Fixed submission:



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


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


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


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


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


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