test/yukicoder/1077.test.cpp

View this file on GitHub
Last update: 2025-11-24 18:49:07+09:00
Problem: https://yukicoder.me/problems/no/1077
Link: View error logs on GitHub Actions

Depends on

Code

#define PROBLEM "https://yukicoder.me/problems/no/1077"
#include <bits/stdc++.h>

#include "library/datastructure/SlopeTrick.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    SlopeTrick<int> ST;
    while (n--) {
        int v;
        std::cin >> v;
        ST.clear_inc();
        ST.add_abs(v);
    }
    std::cout << ST.min_f << std::endl;
}

#line 1 "test/yukicoder/1077.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1077"
#include <bits/stdc++.h>

#line 1 "library/datastructure/SlopeTrick.hpp"
// reference:https://maspypy.com/slope-trick-1-解説編
template <typename T> class SlopeTrick {
    static constexpr T MIN = std::numeric_limits<T>::lowest() / 2;
    static constexpr T MAX = std::numeric_limits<T>::max() / 2;
    std::priority_queue<T> L;
    std::priority_queue<T, std::vector<T>, std::greater<T>> R;
    T add_l, add_r;

    T L0() const { return L.size() ? L.top() + add_l : MIN; }
    T R0() const { return R.size() ? R.top() + add_r : MAX; }
    void push_L(T a) { L.push(a - add_l); }
    void push_R(T a) { R.push(a - add_r); }

  public:
    T min_f;
    SlopeTrick() : add_l(0), add_r(0), min_f(0) {}

    int size() const { return L.size() + R.size(); }

    std::tuple<T, T, T> get_min_range() const { return {L0(), R0(), min_f}; }

    void operator+=(const T &a) { min_f += a; }

    // (x-a)+
    void add_x_minus_a(T a) {
        if (a < L0()) {
            min_f += L0() - a;
            push_R(L0());
            L.pop();
            push_L(a);
        } else
            push_R(a);
    }

    // (a-x)+
    void add_a_minus_x(T a) {
        if (a > R0()) {
            min_f += a - R0();
            push_L(R0());
            R.pop();
            push_R(a);
        } else
            push_L(a);
    }

    // |x-a|
    void add_abs(T a) {
        add_x_minus_a(a);
        add_a_minus_x(a);
    }

    // 増加側を消して、減少側のみにする
    void clear_inc() { R = {}; }
    // 減少側を消して、増加側のみにする
    void clear_dec() { L = {}; }

    // g(x) = min_{x-b <= y <= x-a} f(y)
    void sliding_window_minimum(const T &a, const T &b) {
        add_l += a;
        add_r += b;
    }

    void shift(const T &a) { sliding_window_minimum(a, a); }

    // O(nlogn) n=size
    T operator()(T x) const {
        T y = min_f;
        if (x < L0()) {
            auto L_cpy = L;
            while (L_cpy.size()) {
                T a = L_cpy.top() + add_l;
                L_cpy.pop();
                if (a <= x)
                    break;
                y += a - x;
            }
        }
        if (x > R0()) {
            auto R_cpy = R;
            while (R_cpy.size()) {
                T a = R_cpy.top() + add_r;
                R_cpy.pop();
                if (x <= a)
                    break;
                y += x - a;
            }
        }
        return y;
    }

    // O(mlog(n+m)) n=size,m=g.size()
    SlopeTrick &operator+=(SlopeTrick g) {
        min_f += g.min_f;
        while (g.L.size()) {
            T a = g.L0();
            g.L.pop();
            add_a_minus_x(a);
        }
        while (g.R.size()) {
            T a = g.R0();
            g.R.pop();
            add_x_minus_a(a);
        }
        return *this;
    }

    SlopeTrick operator+(SlopeTrick g) const {
        if (size() < g.size())
            return g += *this;
        return (*this) += g;
    }
};
#line 5 "test/yukicoder/1077.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n;
    SlopeTrick<int> ST;
    while (n--) {
        int v;
        std::cin >> v;
        ST.clear_inc();
        ST.add_abs(v);
    }
    std::cout << ST.min_f << std::endl;
}