結果

問題 No.1297 銅像
ユーザー Kiri8128
提出日時 2021-06-08 23:18:33
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,251 bytes
コンパイル時間 146 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 123,648 KB
最終ジャッジ日時 2024-11-27 06:29:55
合計ジャッジ時間 8,087 ms
ジャッジサーバーID
(参考情報)
judge1 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 9 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

from collections import deque
class CHT(): # Convex Hull Trick, Sorted Lines, Sorted Queries, Min Query
# add_line a
# query x
def __init__(self):
self.Q = deque()
def calc(self, f, x):
return f[0] * x + f[1]
def check(self, f1, f2, f3):
return (f2[0] - f1[0]) * (f3[1] - f2[1]) >= (f2[1] - f1[1]) * (f3[0] - f2[0])
def add_line(self, a, b):
f = (a, b)
while len(self.Q) >= 2 and self.check(self.Q[-2], self.Q[-1], f):
self.Q.pop()
self.Q.append(f)
def query(self, x):
while len(self.Q) >= 2 and self.calc(self.Q[0], x) >= self.calc(self.Q[1], x):
self.Q.popleft()
return self.calc(self.Q[0], x)
class LiChaoTree:
# Min Query
def __init__(self, X): # X: 調 x
X = sorted(list(set(X)))
self.inf = 10 ** 18
self.n = 1 << (len(X) - 1).bit_length()
self.X = X + [self.inf] * (self.n - len(X))
self.D = {a: i for i, a in enumerate(X)}
self.lmr = [(0, 0, 0)] * self.n + [(x, x, x) for x in self.X]
for i in range(1, self.n)[::-1]:
self.lmr[i] = (self.lmr[i*2][0], self.lmr[i*2][2], self.lmr[i*2^1][2])
self.F = [None] * (self.n * 2)
def calc(self, f, x):
return f[0] * x + f[1]
def update(self, i, f):
while 1:
l, m, r = self.lmr[i]
fi = self.F[i]
if fi is None:
self.F[i] = f
return
cl = (fi[0] - f[0]) * l + fi[1] - f[1] > 0
cr = (fi[0] - f[0]) * r + fi[1] - f[1] > 0
if cl and cr:
self.F[i] = f
return
if not cl and not cr:
return
if (fi[0] - f[0]) * m + fi[1] - f[1] > 0:
self.F[i], f = f, fi
cl = not cl
if cl:
i *= 2
else:
i = i * 2 + 1
def query(self, x):
i = self.D[x] + self.n
mi = self.inf
while i > 0:
if self.F[i]:
mi = min(mi, self.calc(self.F[i], x))
i >>= 1
return mi
def add_line(self, a, b): # y = ax + b
f = (a, b)
self.update(1, f)
def debug(self):
print("F =", self.F)
print("X =", self.X)
print("D =", self.D)
print("lmr =", self.lmr)
import sys
input = lambda: sys.stdin.readline().rstrip()
cht = CHT()
cht.add_line(0, 0)
N, C = map(int, input().split())
lct = LiChaoTree([i for i in range(N + 1)])
C *= 2
X = [0] * (N + 1) # i 使 i
Y = [0] * (N + 1) # i
for i in range(1, N + 1):
a, b = map(int, input().split())
a *= 2
b *= 2
z = cht.query(a + C * i) + b + i * a + C // 2 * (i ** 2 - i)
X[i] = z
lct.add_line(a - C // 2 * (2 * i - 1), X[i] - i * a + C // 2 * (i ** 2 - i))
if i == -999:
Y[i] = X[i]
else:
Y[i] = lct.query(i) + C // 2 * i ** 2
cht.add_line(-i, (i ** 2 + i) * C // 2 + Y[i])
print(Y[-1] // 2)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0