結果

問題 No.1077 Noelちゃんと星々4
コンテスト
ユーザー noya2
提出日時 2024-06-23 15:56:42
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 3,268 bytes
コンパイル時間 1,191 ms
コンパイル使用メモリ 121,124 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-23 15:56:46
合計ジャッジ時間 2,021 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 2 "/Users/noya2/Desktop/Noya2_library/data_structure/slope_trick.hpp"

#include <queue>
#include <limits>
#include <functional>
#include <algorithm>

namespace noya2{

template< typename T >
struct slope_trick {
 
    const T INF = std::numeric_limits< T >::max() / 3;
 
    T min_f;
    std::priority_queue<T,std::vector<T>,std::less<>> L;
    std::priority_queue<T,std::vector<T>,std::greater<>> R;
    T add_l, add_r;
 
    void push_R(const T& a) {
        R.push(a - add_r);
    }
 
    T top_R() const {
        if (R.empty()) return INF;
        else return R.top() + add_r;
    }
 
    T pop_R() {
        T val = top_R();
        if (!R.empty()) R.pop();
        return val;
    }
 
    void push_L(const T& a) {
        L.push(a - add_l);
    }
 
    T top_L() const {
        if (L.empty()) return -INF;
        else return L.top() + add_l;
    }
 
    T pop_L() {
        T val = top_L();
        if (!L.empty()) L.pop();
        return val;
    }
 
    size_t size() {
        return L.size() + R.size();
    }
 
    slope_trick() : min_f(0), add_l(0), add_r(0) {}

    T min() const {
        return min_f;
    }
 
    // f(x) += a
    void add_all(const T& a) {
        min_f += a;
    }
 
    // add \_
    // f(x) += max(a - x, 0)
    void add_a_minus_x(const T& a) {
        min_f += std::max(T(0), a - top_R());
        push_R(a);
        push_L(pop_R());
    }
 
    // add _/
    // f(x) += max(x - a, 0)
    void add_x_minus_a(const T& a) {
        min_f += std::max(T(0), top_L() - a);
        push_L(a);
        push_R(pop_L());
    }
 
    // add \/
    // f(x) += abs(x - a)
    void add_abs(const T& a) {
        add_a_minus_x(a);
        add_x_minus_a(a);
    }
 
    // \/ -> \_
    // f_{new} (x) = min f(y) (y <= x)
    void clear_right() {
        while (!R.empty()) R.pop();
    }
 
    // \/ -> _/
    // f_{new} (x) = min f(y) (y >= x)
    void clear_left() {
        while (!L.empty()) L.pop();
    }
 
    // \/ -> \_/
    // f_{new} (x) = min f(y) (x-b <= y <= x-a)
    void shift(const T& a, const T& b) {
        assert(a <= b);
        add_l += a;
        add_r += b;
    }
 
    // \/. -> .\/
    // f_{new} (x) = f(x - a)
    void shift(const T& a) {
        shift(a, a);
    }
 
    // L, R を破壊する
    T get(const T& x) {
        T ret = min_f;
        while (!L.empty()) {
            ret += max(T(0), pop_L() - x);
        }
        while (!R.empty()) {
            ret += max(T(0), x - pop_R());
        }
        return ret;
    }
 
    void merge(slope_trick& st) {
        if (st.size() > size()) {
            std::swap(st.L, L);
            std::swap(st.R, R);
            std::swap(st.add_l, add_l);
            std::swap(st.add_r, add_r);
            std::swap(st.min_f, min_f);
        }
        while (!st.R.empty()) {
            add_x_minus_a(st.pop_R());
        }
        while (!st.L.empty()) {
            add_a_minus_x(st.pop_L());
        }
        min_f += st.min_f;
    }
};

} // namespace noya2
#line 2 "without.cpp"

#include <iostream>

int main(){
    int n; std::cin >> n;
    noya2::slope_trick<long long> st;
    for (int i = 0; i < n; i++) {
        long long y;
        std::cin >> y;
        st.clear_right();
        st.add_abs(y);
    }
    std::cout << st.min() << '\n';
}
0