結果

問題 No.1077 Noelちゃんと星々4
コンテスト
ユーザー baluteshih
提出日時 2026-07-05 18:40:47
言語 C++23(gnu拡張gcc16)
(gcc 16.1.0 + boost 1.90.0)
コンパイル:
g++-16 -O2 -lm -std=gnu++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 17 ms / 2,000 ms
コード長 2,576 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,146 ms
コンパイル使用メモリ 358,636 KB
実行使用メモリ 16,768 KB
最終ジャッジ日時 2026-07-05 18:40:55
合計ジャッジ時間 4,321 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#line 1 "test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1077"
#line 2 "cplibrary/assumption.hpp"

#include <cassert>
#include <bits/stdc++.h>
#line 3 "test.cpp"

#line 2 "cplibrary/DataStructure/Convex/SlopeTrick.hpp"

// reference: htl0s://maspypy.com/slope-trick-1-解説編

template<typename T>
class SlopeTrick {
    using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
    using max_heap = std::priority_queue<T>;
    max_heap pq_l;
    min_heap pq_r;
    T add_l, add_r, min_f;
public:
    SlopeTrick() : add_l(), add_r(), min_f() {}
    T top() { return min_f; }
    std::pair<T, T> top_interval() {
        return {pq_l.empty() ? std::numeric_limits<T>::lowest() : pq_l.top(), pq_r.empty() ? std::numeric_limits<T>::max() : pq_r.top() }; 
    }
    T top_l() const { return pq_l.top() + add_l; }
    T top_r() const { return pq_r.top() + add_r; }
    void add_const(T a) { min_f += a; }
    // add (x - a)+
    void add_x_minus_a(T a) {
        if (!pq_l.empty() && top_l() > a) {
            T l0 = top_l();
            min_f += l0 - a;
            pq_l.pop(), pq_r.push(l0 - add_r);
            pq_l.push(a - add_l);
        }
        else pq_r.push(a - add_r);
    }
    // add (a - x)+
    void add_a_minus_x(T a) {
        if (!pq_r.empty() && top_r() < a) {
            T r0 = top_r();
            min_f += a - r0;
            pq_r.pop(), pq_l.push(r0 - add_l);
            pq_r.push(a - add_r);
        }
        else pq_l.push(a - add_l);
    }
    // add |x - a|
    void add_abs(T a) {
        add_x_minus_a(a), add_a_minus_x(a); 
    }
    // add ax + b, O(|a| log n)
    void add_linear(int a, T b) {
        for (min_f += b; a > 0 && !pq_l.empty(); --a) {
            T l0 = top_l();
            min_f += l0;
            pq_l.pop(), pq_r.push(l0 - add_r);
        }
        for (; a < 0 && !pq_r.empty(); ++a) {
            T r0 = top_r();
            min_f -= r0;
            pq_r.pop(), pq_l.push(r0 - add_l);
        }
    }
    void shift(T a) { add_l += a, add_r += a; }
    // g(x) = min_{x-b <= y <= x-a} f(y)
    void sliding_window_minimum(T a, T b) {
        assert(a <= b);
        add_l += a, add_r += b;
    }
    void prefix_min() { min_heap().swap(pq_r); }
    void suffix_min() { max_heap().swap(pq_l); }
};
#line 5 "test.cpp"

int main() {
    std::ios::sync_with_stdio(0), std::cin.tie(0);
    int n;
    std::cin >> n;
    SlopeTrick<int> slope;
    while (n--) {
        int x;
        std::cin >> x;
        slope.prefix_min();
        slope.add_abs(x);
    }
    std::cout << slope.top() << "\n";
}
0