結果

問題 No.2304 Distinct Elements
コンテスト
ユーザー kwm_t
提出日時 2023-05-13 02:19:36
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 77 ms / 3,000 ms
コード長 5,137 bytes
コンパイル時間 2,238 ms
コンパイル使用メモリ 207,412 KB
最終ジャッジ日時 2025-02-12 23:46:01
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 58
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function ‘std::vector<long long int> SlopeTrick::Fx(std::vector<long long int>&)’:
main.cpp:108:9: warning: no return statement in function returning non-void [-Wreturn-type]
  108 |         }
      |         ^

ソースコード

diff # 

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n-1); i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define endl "\n"
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
#include "bits/stdc++.h"
//#include "atcoder/all"
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = (int)1e9;
const long long LINF = (long long)1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n-1); i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r-1);i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define endl "\n"

struct SlopeTrick {
	//コンストラクタ
	SlopeTrick() :minf(0), addR(0), addL(0) {}

	//max(0,x-a)を加算する
	void pushR(long long a) {
		if (0 == Lque.size()) {
			Rque.push(a - addR);
		}
		else {
			long long l0 = Lque.top() + addL;
			Lque.push(a - addL);
			long long x = Lque.top() + addL;
			Lque.pop();
			Rque.push(x - addR);
			minf += max((long long)0, l0 - a);
		}
	}
	//max(0,a-x)を加算する
	void pushL(long long a) {
		if (0 == Rque.size()) {
			Lque.push(a - addL);
		}
		else {
			long long r0 = Rque.top() + addR;
			Rque.push(a - addR);
			long long x = Rque.top() + addR;
			Rque.pop();
			Lque.push(x - addL);
			minf += max((long long)0, a - r0);
		}
	}
	//max(x-a,a-x)を加算する
	void push(long long a) { pushR(a); pushL(a); }
	//定数追加
	void addmin(long long a) { minf += a; }
	//傾きが0の区間の両端
	pair<long long, long long> getZero() {
		pair<long long, long long>p = { -LINF,LINF };
		if (0 != Lque.size()) { p.first = Lque.top() + addL; }
		if (0 != Rque.size()) { p.second = Rque.top() + addR; }
		return p;
	}
	//累積min
	void CumulativeMin() { Rque = priority_queue<long long, vector<long long>, greater<long long>>(); }
	//右側累積min
	void CumulativeMinR() { Lque = priority_queue<long long>(); }
	//関数の復元(遅い。非推奨？)
	vector<long long> Fx(vector<long long> &X) {
		vector<long long>vL;
		vector<long long>vR;
		vector<long long>ret(X.size());
		while (!Lque.empty()) {
			vL.push_back(Lque.top() + addL);
			Lque.pop();
		}
		while (!Rque.empty()) {
			vR.push_back(Rque.top() + addR);
			Rque.pop();
		}
		rep(i, X.size()) {
			long long num = minf;
			rep(j, vL.size()) { num += max((long long)0, vL[j] - X[i]); }
			rep(j, vR.size()) { num += max((long long)0, X[i] - vR[j]); }
			X[i] = num;
		}
		//元に戻す必要があれば
		//rep(i, vL.size()) { Lque.push(vL[i] - addL); }
		//rep(i, vR.size()) { Rque.push(vR[i] - addR); }
	}
	//関数の復元(遅い。非推奨？)
	long long FxSimple(long long X) {
		vector<long long>vL;
		vector<long long>vR;
		long long ret = minf;
		while (!Lque.empty()) {
			ret += max((long long)0, (Lque.top() + addL) - X);
			Lque.pop();
		}
		while (!Rque.empty()) {
			ret += max((long long)0, X - (Rque.top() + addR));
			Rque.pop();
		}
		return ret;
	}
	//右側スライド
	void SlideR(long long x) { addR += x; }
	//左側スライド
	void SlideL(long long x) { addL += x; }
	//全体スライド(無制限)
	void Slid(long long x) { SlideL(x), SlideR(x); };
	//全体スライド(a <= bでないと壊れる)
	//g(x) = min f(y) y∈[x-b,x-a]
	void Slid(long long b, long long a) { SlideL(a), SlideR(b); };
	//マージ(マージ元は以降使えなくなる。)
	void merge(SlopeTrick &st) {
		if ((Lque.size() + Rque.size()) < (st.Lque.size() + st.Rque.size())) {
			swap(Lque, st.Lque);
			swap(Rque, st.Rque);
			swap(minf, st.minf);
			swap(addR, st.addR);
			swap(addL, st.addL);
		}
		while (!st.Lque.empty()) {
			pushL(st.Lque.top() + st.addL);
			st.Lque.pop();
		}
		while (!st.Rque.empty()) {
			pushR(st.Rque.top() + st.addR);
			st.Rque.pop();
		}
		minf += st.minf;
	}

	priority_queue<long long> Lque;	//左側(大きい順)
	priority_queue<long long, vector<long long>, greater<long long>> Rque;	//右側(小さい順)
	long long minf;					//最小値
	long long addR;					//右側集合全てにたされる数
	long long addL;					//左側集合全てにたされる数
};
int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	vector<int>a(n);
	rep(i, n)cin >> a[i];
	sort(all(a));
	SlopeTrick st;
	rep(i, n) {
		if (0 != i) {
			st.Slid(1);
			st.CumulativeMin();
		}
		st.push(a[i]);
	}
	cout << st.minf << endl;
	return 0;
}
0