結果

問題 No.2458 Line Up Charged Balls
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:56:05
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,302 bytes
コンパイル時間 246 ms
コンパイル使用メモリ 82,052 KB
実行使用メモリ 141,460 KB
最終ジャッジ日時 2025-06-12 14:58:14
合計ジャッジ時間 5,392 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 1 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import inf

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

    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.root = LiChaoNode(x_min, x_max)
    
    def insert(self, new_line):
        def _insert(node, new_line):
            if node.line is None:
                node.line = new_line
                return
            l, r = node.l, node.r
            m = (l + r) // 2
            curr_val = node.line.get(m)
            new_val = new_line.get(m)
            if new_val > curr_val:
                node.line, new_line = new_line, node.line
            if l == r:
                return
            if new_line.get(l) > node.line.get(l):
                if not node.left:
                    node.left = LiChaoNode(l, m)
                _insert(node.left, new_line)
            elif new_line.get(r) > node.line.get(r):
                if not node.right:
                    node.right = LiChaoNode(m + 1, r)
                _insert(node.right, new_line)
        _insert(self.root, new_line)
    
    def query(self, x):
        def _query(node, x):
            if not node:
                return -inf
            res = node.line.get(x) if node.line else -inf
            l, r = node.l, node.r
            m = (l + r) // 2
            if x <= m:
                res = max(res, _query(node.left, x))
            else:
                res = max(res, _query(node.right, x))
            return res
        return _query(self.root, x)

def main():
    input = sys.stdin.read().split()
    N = int(input[0])
    Q = list(map(int, input[1:N+1]))
    if N == 1:
        print(0)
        return
    # Initial x range: considering possible Q[i] up to 1e5 in absolute value
    tree = LiChaoTree(-10**5, 10**5)
    tree.insert(Line(Q[0], 0))
    max_ans = -inf
    for i in range(1, N):
        x = Q[i]
        current = tree.query(x)
        if current > max_ans:
            max_ans = current
        tree.insert(Line(Q[i], current))
    print(max_ans)

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