結果

問題 No.2304 Distinct Elements
ユーザー KudeKude
提出日時 2023-05-12 23:04:31
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 51 ms / 3,000 ms
コード長 2,397 bytes
コンパイル時間 2,794 ms
コンパイル使用メモリ 233,204 KB
実行使用メモリ 6,264 KB
最終ジャッジ日時 2024-05-06 13:06:15
合計ジャッジ時間 5,996 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 40 ms
6,140 KB
testcase_05 AC 43 ms
6,140 KB
testcase_06 AC 42 ms
6,264 KB
testcase_07 AC 39 ms
6,140 KB
testcase_08 AC 39 ms
6,136 KB
testcase_09 AC 47 ms
6,136 KB
testcase_10 AC 51 ms
6,140 KB
testcase_11 AC 49 ms
6,136 KB
testcase_12 AC 50 ms
6,136 KB
testcase_13 AC 49 ms
6,260 KB
testcase_14 AC 2 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 2 ms
5,376 KB
testcase_23 AC 2 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 2 ms
5,376 KB
testcase_29 AC 35 ms
5,936 KB
testcase_30 AC 4 ms
5,376 KB
testcase_31 AC 27 ms
5,376 KB
testcase_32 AC 35 ms
5,968 KB
testcase_33 AC 4 ms
5,376 KB
testcase_34 AC 36 ms
5,980 KB
testcase_35 AC 41 ms
6,056 KB
testcase_36 AC 3 ms
5,376 KB
testcase_37 AC 14 ms
5,376 KB
testcase_38 AC 41 ms
6,252 KB
testcase_39 AC 41 ms
6,136 KB
testcase_40 AC 24 ms
5,876 KB
testcase_41 AC 14 ms
5,376 KB
testcase_42 AC 32 ms
6,264 KB
testcase_43 AC 45 ms
6,132 KB
testcase_44 AC 34 ms
6,036 KB
testcase_45 AC 26 ms
5,376 KB
testcase_46 AC 21 ms
5,376 KB
testcase_47 AC 2 ms
5,376 KB
testcase_48 AC 2 ms
5,376 KB
testcase_49 AC 39 ms
6,140 KB
testcase_50 AC 41 ms
6,136 KB
testcase_51 AC 41 ms
6,136 KB
testcase_52 AC 37 ms
6,136 KB
testcase_53 AC 26 ms
6,136 KB
testcase_54 AC 34 ms
6,136 KB
testcase_55 AC 35 ms
6,264 KB
testcase_56 AC 34 ms
6,040 KB
testcase_57 AC 38 ms
6,264 KB
testcase_58 AC 36 ms
6,132 KB
testcase_59 AC 34 ms
6,264 KB
testcase_60 AC 1 ms
5,376 KB
testcase_61 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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