結果
問題 | No.738 平らな農地 |
ユーザー |
|
提出日時 | 2022-03-01 15:01:52 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 554 ms / 2,000 ms |
コード長 | 6,246 bytes |
コンパイル時間 | 2,977 ms |
コンパイル使用メモリ | 215,208 KB |
最終ジャッジ日時 | 2025-01-28 04:06:19 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 87 |
ソースコード
#include <bits/stdc++.h>#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) (x).begin(), (x).end()#define sz(x) int(x.size())#define yn(joken) cout<<((joken) ? "Yes" : "No")<<endl#define YN(joken) cout<<((joken) ? "YES" : "NO")<<endlusing namespace std;using ll = long long;using vi = vector<int>;using vl = vector<ll>;using vs = vector<string>;using vc = vector<char>;using vd = vector<double>;using vvi = vector<vector<int>>;using vvl = vector<vector<ll>>;using vvd = vector<vector<double>>;const int INF = 1e9;const ll LINF = 1e18;template <class T>bool chmax(T& a, const T& b) {if (a < b) {a = b;return 1;}return 0;}template <class T>bool chmin(T& a, const T& b) {if (b < a) {a = b;return 1;}return 0;}template <class T>vector<T> make_vec(size_t a) {return vector<T>(a);}template <class T, class... Ts>auto make_vec(size_t a, Ts... ts) {return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));}template <typename T>istream& operator>>(istream& is, vector<T>& v) {for (int i = 0; i < int(v.size()); i++) {is >> v[i];}return is;}template <typename T>ostream& operator<<(ostream& os, const vector<T>& v) {for (int i = 0; i < int(v.size()); i++) {os << v[i];if (i < int(v.size()) - 1) os << ' ';}return os;}// すでに追加したものを削除できるslope trick// Query query(): Query{lx,rx,min_f}を返す,[lx,rx]でmin_fを取る// add_all(T a): f(x)にaを加算する// add_a_minus_x(T a): f(x)にmax(a-x,0)を加算する, \_// add_x_minus_a(T a): f(x)にmax(x-a,0)を加算する, _/// add_abs(T a): f(x)に|x-a|を加算する, \/// erase_a_minus_x(T a): f(x)からmax(a-x,0)を削除する, \_// erase_x_minus_a(T a): f(x)からmax(x-a,0)を削除する, _/// erase_abs(T a): f(x)から|x-a|を削除する, \/// clear_right(): f(x)<-min(f(t)),t<=x , \_/ -> \_// clear_left(): f(x)<-min(f(t)),x<=t , \_/ -> _/// shift(T a,T b): f(x)<-min(f(t)),x-b<=t<=x-a// shift(T a): f(x)<-f(x-a),shift(a,a)してるだけ// get(T x): f(x)を返す, fを破壊しO(sz(L)+sz(R))// merge(SlopeTrick x): f(x)にg(x)を加算する, gを破壊するtemplate <typename T>struct ErasableSlopeTrick{const T INF = numeric_limits<T>::max() / 3;set<T> S_l,S_r;map<T,T> mp_l,mp_r;T min_f, offset_l, offset_r;private:void insert_R(const T &a){S_r.insert(a - offset_r);mp_r[a - offset_r]++;}T top_R() const{if (S_r.empty()) return INF;else return *S_r.begin() + offset_r;}T pop_R(){T val = top_R();if (!S_r.empty()){mp_r[val]--;if(mp_r[val]==0) S_r.erase(val);}return val;}void insert_L(const T &a){S_l.insert(a - offset_l);mp_l[a - offset_l]++;}T top_L() const{if (S_l.empty()) return -INF;else return *--S_l.end() + offset_l;}T pop_L(){T val = top_L();if (!S_l.empty()){mp_l[val]--;if(mp_l[val]==0) S_l.erase(val);}return val;}size_t size(){return S_l.size() + S_r.size();}public:ErasableSlopeTrick() : min_f(0), offset_l(0), offset_r(0) {}struct Query{T lx, rx, min_f;};Query query() const{return (Query){top_L(), top_R(), min_f};}void add_all(const T &a){min_f += a;}void add_a_minus_x(const T &a){insert_R(a);insert_L(pop_R());min_f += max(T(0), a - top_L());}void add_x_minus_a(const T &a){insert_L(a);insert_R(pop_L());min_f += max(T(0), top_R() - a);}void add_abs(const T &a){add_a_minus_x(a);add_x_minus_a(a);}void erase_a_minus_x(const T &a){if(S_l.find(a - offset_l)==S_l.end()){mp_r[a - offset_r]--;if(mp_r[a - offset_r]==0) S_r.erase(a - offset_r);insert_R(pop_L());}else{mp_l[a - offset_l]--;if(mp_l[a - offset_l]==0) S_l.erase(a - offset_l);}min_f -= max(T(0), a - top_R());}void erase_x_minus_a(const T &a){if(S_l.find(a - offset_l)==S_l.end()){mp_r[a - offset_r]--;if(mp_r[a - offset_r]==0) S_r.erase(a - offset_r);}else{mp_l[a - offset_l]--;if(mp_l[a- offset_l]==0) S_l.erase(a - offset_l);insert_L(pop_R());}min_f -= max(T(0), top_L() - a);}void erase_abs(const T &a){erase_a_minus_x(a);erase_x_minus_a(a);}void clear_right(){if(!S_r.empty()) S_r.clear();}void clear_left(){if(!S_l.empty()) S_l.clear();}void shift(const T &a, const T &b){assert(a <= b);offset_l += a;offset_r += b;}void shift(const T &a){shift(a, a);}T get(const T &x){T ret = min_f;while (!S_l.empty()) ret += max(T(0), pop_L() - x);while (!S_r.empty()) ret += max(T(0), x - pop_R());return ret;}void merge(ErasableSlopeTrick &st){if (st.size() > size()){swap(st.S_l, S_l);swap(st.S_r, S_r);swap(st.min_f, min_f);swap(st.offset_l, offset_l);swap(st.offset_r, offset_r);}while (!st.S_r.empty()) add_x_minus_a(st.pop_R());while (!st.S_l.empty()) add_a_minus_x(st.pop_L());min_f += st.min_f;}};int main(){cin.tie(nullptr);ios::sync_with_stdio(false);int N,K;cin>>N>>K;vl A(N);cin>>A;queue<ll> Q;ErasableSlopeTrick<ll> EST;ll ans=LINF;rep(i,N){EST.add_abs(A[i]);Q.push(A[i]);while(sz(Q)>K){auto a=Q.front();EST.erase_abs(a);Q.pop();}if(sz(Q)==K){auto ret=EST.query();chmin(ans,ret.min_f);}}cout<<ans<<endl;}