結果
問題 | No.1077 Noelちゃんと星々4 |
ユーザー | 草苺奶昔 |
提出日時 | 2023-03-10 19:53:31 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 101 ms / 2,000 ms |
コード長 | 4,378 bytes |
コンパイル時間 | 306 ms |
コンパイル使用メモリ | 82,376 KB |
実行使用メモリ | 78,176 KB |
最終ジャッジ日時 | 2024-09-18 03:22:11 |
合計ジャッジ時間 | 2,971 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 60 ms
68,112 KB |
testcase_01 | AC | 62 ms
67,024 KB |
testcase_02 | AC | 89 ms
77,792 KB |
testcase_03 | AC | 94 ms
78,116 KB |
testcase_04 | AC | 76 ms
71,544 KB |
testcase_05 | AC | 66 ms
71,052 KB |
testcase_06 | AC | 74 ms
72,716 KB |
testcase_07 | AC | 76 ms
73,316 KB |
testcase_08 | AC | 72 ms
71,496 KB |
testcase_09 | AC | 71 ms
70,636 KB |
testcase_10 | AC | 96 ms
78,092 KB |
testcase_11 | AC | 86 ms
77,848 KB |
testcase_12 | AC | 85 ms
77,676 KB |
testcase_13 | AC | 67 ms
68,924 KB |
testcase_14 | AC | 94 ms
77,640 KB |
testcase_15 | AC | 88 ms
77,896 KB |
testcase_16 | AC | 68 ms
71,556 KB |
testcase_17 | AC | 90 ms
77,888 KB |
testcase_18 | AC | 96 ms
77,888 KB |
testcase_19 | AC | 67 ms
68,696 KB |
testcase_20 | AC | 63 ms
67,892 KB |
testcase_21 | AC | 101 ms
78,176 KB |
ソースコード
from heapq import heappop, heappush from typing import Tuple INF = int(1e18) class SlopeTrick: __slots__ = ("_min_f", "_pq_l", "_pq_r", "add_l", "add_r") def __init__(self): self.add_l = 0 # 左侧第一个拐点的位置 -> \_/ self.add_r = 0 # 右侧第一个拐点的位置 \_/ <- self._pq_l = [] # 大根堆 self._pq_r = [] # 小根堆 self._min_f = 0 def query(self) -> Tuple[int, int, int]: """返回 `f(x)的最小值, f(x)取得最小值时x的最小值和x的最大值`""" return self._min_f, self._top_l(), self._top_r() def add_all(self, a: int) -> None: """f(x) += a""" self._min_f += a def add_a_minus_x(self, a: int) -> None: """ ``` add \\__ f(x) += max(a - x, 0) ``` """ tmp = a - self._top_r() if tmp > 0: self._min_f += tmp self._push_r(a) self._push_l(self._pop_r()) def add_x_minus_a(self, a: int) -> None: """ ``` add __/ f(x) += max(x - a, 0) ``` """ tmp = self._top_l() - a if tmp > 0: self._min_f += tmp self._push_l(a) self._push_r(self._pop_l()) def add_abs(self, a: int) -> None: """ ``` add \\/ f(x) += abs(x - a) ``` """ self.add_a_minus_x(a) self.add_x_minus_a(a) def clear_right(self) -> None: """ 取前缀最小值. ``` \\/ -> \\_ f_{new} (x) = min f(y) (y <= x) ``` """ while self._pq_r: self._pq_r.pop() def clear_left(self) -> None: """ 取后缀最小值. ``` \\/ -> _/ f_{new} (x) = min f(y) (y >= x) ``` """ while self._pq_l: self._pq_l.pop() def shift(self, a: int, b: int) -> None: """ ``` \\/ -> \\_/ f_{new} (x) = min f(y) (x-b <= y <= x-a) ``` """ assert a <= b self.add_l += a self.add_r += b def translate(self, a: int) -> None: """ 函数向右平移a ``` \\/. -> .\\/ f_{new} (x) = f(x - a) ``` """ self.shift(a, a) def get_destructive(self, x: int) -> int: """ y = f(x), f(x) broken 会破坏f内部左右两边的堆. """ res = self._min_f while self._pq_l: tmp = self._pop_l() - x if tmp > 0: res += tmp while self._pq_r: tmp = x - self._pop_r() if tmp > 0: res += tmp return res def merge_destructive(self, st: "SlopeTrick"): """ f(x) += g(x), g(x) broken 会破坏g(x)的左右两边的堆. """ if len(st) > len(self): st._pq_l, self._pq_l = self._pq_l, st._pq_l st._pq_r, self._pq_r = self._pq_r, st._pq_r st.add_l, self.add_l = self.add_l, st.add_l st.add_r, self.add_r = self.add_r, st.add_r st._min_f, self._min_f = self._min_f, st._min_f while st._pq_r: self.add_x_minus_a(st._pop_r()) while st._pq_l: self.add_a_minus_x(st._pop_l()) self._min_f += st._min_f def _push_r(self, a: int) -> None: heappush(self._pq_r, a - self.add_r) def _top_r(self) -> int: if not self._pq_r: return INF return self._pq_r[0] + self.add_r def _pop_r(self) -> int: val = self._top_r() if self._pq_r: heappop(self._pq_r) return val def _push_l(self, a: int) -> None: heappush(self._pq_l, -a + self.add_l) def _top_l(self) -> int: if not self._pq_l: return -INF return -self._pq_l[0] + self.add_l def _pop_l(self) -> int: val = self._top_l() if self._pq_l: heappop(self._pq_l) return val def _size(self) -> int: return len(self._pq_l) + len(self._pq_r) def __len__(self) -> int: return self._size() n = int(input()) heights = list(map(int, input().split())) sl = SlopeTrick() for num in heights: sl.add_abs(num) sl.clear_right() res = sl.query() print(res[0])