結果

問題 No.2304 Distinct Elements
コンテスト
ユーザー Kude
提出日時 2023-05-12 23:04:31
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 46 ms / 3,000 ms
コード長 2,397 bytes
コンパイル時間 2,160 ms
コンパイル使用メモリ 223,020 KB
最終ジャッジ日時 2025-02-12 23:31:36
ジャッジサーバーID
（参考情報） 		judge3 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 58
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
namespace {
#pragma GCC diagnostic ignored "-Wunused-function"
#include<atcoder/all>
#pragma GCC diagnostic warning "-Wunused-function"
using namespace std;
using namespace atcoder;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
template<class T> bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
template<class T> bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; }
using ll = long long;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<VI>;
using VL = vector<ll>;
using VVL = vector<VL>;

template<class T=long long>
struct SlopeTrick {
    static constexpr T INF = std::numeric_limits<T>::max() / 3;
    T min_f = 0;

    // acutual value of x in L is ADD_add_L(x) = x + add_L
    T add_L = 0, add_R = 0;
    std::priority_queue<T> L;
    std::priority_queue<T, std::vector<T>, std::greater<>> R;

    T top_L() { return L.empty() ? -INF : L.top() + add_L; }
    T top_R() { return R.empty() ? +INF : R.top() + add_R; }
    void push_L(T x) { L.push(x - add_L); }
    void push_R(T x) { R.push(x - add_R); }
    T pushpop_L(T x) {
        T L_max = top_L();
        if (x >= L_max) return x;
        L.pop();
        push_L(x);
        return L_max;
    }
    T pushpop_R(T x) {
        T R_min = top_R();
        if (x <= R_min) return x;
        R.pop();
        push_R(x);
        return R_min;
    }

    // f(x) += c
    void add_constant(T c) { min_f += c; }
    // f(x) += max(x - a, 0)
    void add_right_slope(T a) {
        min_f += std::max<T>(top_L() - a, 0);
        push_R(pushpop_L(a));
    }
    // f(x) += max(a - x, 0)
    void add_left_slope(T a) {
        min_f += std::max<T>(a - top_R(), 0);
        push_L(pushpop_R(a));
    }
    // f(x) += abs(x - a)
    void add_v(T a) { add_right_slope(a); add_left_slope(a); }

    void shift(T a, T b) { 
        assert(a <= b);
        add_L += a;
        add_R += b;
    }
    void shift(T a) { shift(a, a); }
};

} int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  VI a(n);
  rep(i, n) cin >> a[i];
  sort(all(a));
  SlopeTrick st;
  for(int x: a) {
    st.shift(1);
    while(!st.R.empty()) st.R.pop();
    st.add_v(x);
  }
  cout << st.min_f << '\n';
}
0