結果

問題 No.1077 Noelちゃんと星々4
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-10 19:53:31
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 105 ms / 2,000 ms
コード長 4,378 bytes
コンパイル時間 2,090 ms
コンパイル使用メモリ 81,312 KB
実行使用メモリ 77,620 KB
最終ジャッジ日時 2023-10-18 06:47:42
合計ジャッジ時間 3,905 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 63 ms
67,596 KB
testcase_01 AC 65 ms
67,596 KB
testcase_02 AC 95 ms
77,256 KB
testcase_03 AC 99 ms
77,388 KB
testcase_04 AC 72 ms
72,228 KB
testcase_05 AC 67 ms
70,024 KB
testcase_06 AC 74 ms
72,240 KB
testcase_07 AC 76 ms
72,368 KB
testcase_08 AC 71 ms
72,224 KB
testcase_09 AC 70 ms
70,180 KB
testcase_10 AC 99 ms
77,416 KB
testcase_11 AC 90 ms
77,188 KB
testcase_12 AC 89 ms
77,104 KB
testcase_13 AC 69 ms
69,652 KB
testcase_14 AC 99 ms
77,252 KB
testcase_15 AC 88 ms
77,108 KB
testcase_16 AC 72 ms
72,228 KB
testcase_17 AC 89 ms
77,204 KB
testcase_18 AC 99 ms
77,336 KB
testcase_19 AC 67 ms
69,652 KB
testcase_20 AC 62 ms
67,604 KB
testcase_21 AC 105 ms
77,620 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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])
0