結果

問題 No.2458 Line Up Charged Balls
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:49:58
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,840 bytes
コンパイル時間 4,526 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 141,328 KB
最終ジャッジ日時 2025-04-15 22:51:37
合計ジャッジ時間 6,669 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 5 WA * 1 TLE * 1 -- * 18
権限があれば一括ダウンロードができます

ソースコード

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 LiChaoTree:
    def __init__(self, x_min, x_max):
        self.x_min = x_min
        self.x_max = x_max
        self.nodes = []
        self.nodes.append({'l': x_min, 'r': x_max, 'line': None, 'left': -1, 'right': -1})

    def insert_line(self, new_line):
        stack = [0]
        while stack:
            node_idx = stack.pop()
            node = self.nodes[node_idx]
            l, r = node['l'], node['r']
            if node['line'] is None:
                node['line'] = new_line
                continue
            current_line = node['line']
            m = (l + r) // 2

            cl_l = current_line.get(l)
            nl_l = new_line.get(l)
            cl_r = current_line.get(r)
            nl_r = new_line.get(r)

            if nl_l > cl_l and nl_r > cl_r:
                node['line'] = new_line
                continue
            if nl_l <= cl_l and nl_r <= cl_r:
                continue

            cl_m = current_line.get(m)
            nl_m = new_line.get(m)

            if nl_m > cl_m:
                node['line'], new_line = new_line, current_line

            if new_line.get(l) > current_line.get(l):
                if node['left'] == -1:
                    new_node = {'l': l, 'r': m, 'line': None, 'left': -1, 'right': -1}
                    self.nodes.append(new_node)
                    node['left'] = len(self.nodes) - 1
                stack.append(node['left'])
            else:
                if node['right'] == -1:
                    new_node = {'l': m + 1, 'r': r, 'line': None, 'left': -1, 'right': -1}
                    self.nodes.append(new_node)
                    node['right'] = len(self.nodes) - 1
                stack.append(node['right'])

    def query(self, x):
        res = -float('inf')
        node_idx = 0
        while node_idx != -1:
            node = self.nodes[node_idx]
            line = node['line']
            if line is not None:
                res = max(res, line.get(x))
            m = (node['l'] + node['r']) // 2
            if x <= m:
                next_node = node['left']
            else:
                next_node = node['right']
            node_idx = next_node
        return res

def main():
    import sys
    input = sys.stdin.read().split()
    N = int(input[0])
    Q = list(map(int, input[1:N+1]))
    
    tree = LiChaoTree(-10**18, 10**18)
    max_E = -float('inf')
    
    for i in range(N):
        q = Q[i]
        if i == 0:
            tree.insert_line(Line(q, 0))
        else:
            current = tree.query(q)
            tree.insert_line(Line(q, current))
            if current > max_E:
                max_E = current
    print(max_E)

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