結果

問題 No.2458 Line Up Charged Balls
コンテスト
ユーザー lam6er
提出日時 2025-04-16 16:01:30
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,527 bytes
コンパイル時間 315 ms
コンパイル使用メモリ 81,520 KB
実行使用メモリ 140,788 KB
最終ジャッジ日時 2025-04-16 16:05:07
合計ジャッジ時間 8,227 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20 WA * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class Line:
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def get(self, x):
        return self.a * x + self.b

class LiChaoNode:
    def __init__(self, l, r):
        self.l = l
        self.r = r
        self.left = None
        self.right = None
        self.line = None

class LiChaoTree:
    def __init__(self, x_min, x_max):
        self.x_min = x_min
        self.x_max = x_max
        self.root = LiChaoNode(x_min, x_max)

    def insert_line(self, new_line):
        stack = [(self.root, new_line)]
        while stack:
            node, line = stack.pop()
            l = node.l
            r = node.r
            m = (l + r) // 2
            if node.line is None:
                node.line = line
                continue
            current_val = node.line.get(m)
            new_val = line.get(m)
            if new_val > current_val:
                node.line, line = line, node.line
            current_val_l = node.line.get(l)
            new_val_l = line.get(l)
            current_val_r = node.line.get(r)
            new_val_r = line.get(r)
            if new_val_l > current_val_l:
                if node.left is None:
                    node.left = LiChaoNode(l, m)
                stack.append((node.left, line))
            if new_val_r > current_val_r:
                if node.right is None:
                    node.right = LiChaoNode(m + 1, r)
                stack.append((node.right, line))

    def query_max(self, x):
        res = -float('inf')
        stack = [self.root]
        while stack:
            node = stack.pop()
            if node is None:
                continue
            if node.line is not None:
                res = max(res, node.line.get(x))
            m = (node.l + node.r) // 2
            if x <= m:
                stack.append(node.left)
            else:
                stack.append(node.right)
        return res

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    Q = list(map(int, input[1:N+1]))
    if N < 2:
        print(0)
        return
    x_min = -10**5
    x_max = 10**5
    tree = LiChaoTree(x_min, x_max)
    first_line = Line(Q[0], 0)
    tree.insert_line(first_line)
    max_ans = -float('inf')
    for i in range(1, N):
        x = Q[i]
        current_max = tree.query_max(x)
        if current_max > max_ans:
            max_ans = current_max
        new_line = Line(Q[i], current_max)
        tree.insert_line(new_line)
    print(max_ans)

if __name__ == "__main__":
    main()
0