#869094 (C++17) No.2304 Distinct Elements

• 問題: No.2304 Distinct Elements
• ユーザー: kwm_t
• 提出日時: 2023-05-13 02:19:36
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 69 ms / 3,000 ms
• コード長: 5,137 bytes
• コンパイル時間: 2,245 ms
• コンパイル使用メモリ: 213,608 KB
• 実行使用メモリ: 6,264 KB
• 最終ジャッジ日時: 2024-05-06 15:01:54
• 合計ジャッジ時間: 5,867 ms
• ジャッジサーバーID （参考情報）: judge5 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	1 ms; 5,376 KB
testcase_02	AC	2 ms; 5,376 KB
testcase_03	AC	2 ms; 5,376 KB
testcase_04	AC	49 ms; 6,136 KB
testcase_05	AC	48 ms; 6,136 KB
testcase_06	AC	49 ms; 6,136 KB
testcase_07	AC	48 ms; 6,260 KB
testcase_08	AC	48 ms; 6,132 KB
testcase_09	AC	68 ms; 6,132 KB
testcase_10	AC	67 ms; 6,260 KB
testcase_11	AC	67 ms; 6,264 KB
testcase_12	AC	66 ms; 6,260 KB
testcase_13	AC	69 ms; 6,264 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	1 ms; 5,376 KB
testcase_18	AC	1 ms; 5,376 KB
testcase_19	AC	2 ms; 5,376 KB
testcase_20	AC	1 ms; 5,376 KB
testcase_21	AC	2 ms; 5,376 KB
testcase_22	AC	2 ms; 5,376 KB
testcase_23	AC	1 ms; 5,376 KB
testcase_24	AC	2 ms; 5,376 KB
testcase_25	AC	1 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	40 ms; 5,936 KB
testcase_30	AC	5 ms; 5,376 KB
testcase_31	AC	32 ms; 5,376 KB
testcase_32	AC	52 ms; 6,096 KB
testcase_33	AC	6 ms; 5,376 KB
testcase_34	AC	54 ms; 6,088 KB
testcase_35	AC	59 ms; 5,936 KB
testcase_36	AC	5 ms; 5,376 KB
testcase_37	AC	16 ms; 5,376 KB
testcase_38	AC	50 ms; 6,112 KB
testcase_39	AC	51 ms; 6,132 KB
testcase_40	AC	29 ms; 5,872 KB
testcase_41	AC	16 ms; 5,376 KB
testcase_42	AC	40 ms; 6,136 KB
testcase_43	AC	53 ms; 6,132 KB
testcase_44	AC	49 ms; 5,912 KB
testcase_45	AC	38 ms; 5,376 KB
testcase_46	AC	29 ms; 5,376 KB
testcase_47	AC	2 ms; 5,376 KB
testcase_48	AC	2 ms; 5,376 KB
testcase_49	AC	52 ms; 6,264 KB
testcase_50	AC	52 ms; 6,132 KB
testcase_51	AC	50 ms; 6,136 KB
testcase_52	AC	47 ms; 6,136 KB
testcase_53	AC	44 ms; 6,136 KB
testcase_54	AC	44 ms; 6,132 KB
testcase_55	AC	43 ms; 6,136 KB
testcase_56	AC	41 ms; 6,252 KB
testcase_57	AC	51 ms; 6,140 KB
testcase_58	AC	49 ms; 6,140 KB
testcase_59	AC	43 ms; 6,136 KB
testcase_60	AC	2 ms; 5,376 KB
testcase_61	AC	1 ms; 5,376 KB

コンパイルメッセージ

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 |         }
      |         ^

ソースコード

#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;
}