結果
| 問題 | 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 | }
| ^
ソースコード
#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;}//累積minvoid CumulativeMin() { Rque = priority_queue<long long, vector<long long>, greater<long long>>(); }//右側累積minvoid 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;}