#578126 (C++17) No.738 平らな農地

• 問題: No.738 平らな農地
• ユーザー: iiljj
• 提出日時: 2020-11-10 00:06:00
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 490 ms / 2,000 ms
• コード長: 21,829 bytes
• コンパイル時間: 2,369 ms
• コンパイル使用メモリ: 215,284 KB
• 実行使用メモリ: 9,596 KB
• 最終ジャッジ日時: 2023-09-29 23:06:05
• 合計ジャッジ時間: 25,055 ms
• ジャッジサーバーID （参考情報）: judge13 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,376 KB
testcase_01	AC	1 ms; 4,380 KB
testcase_02	AC	1 ms; 4,376 KB
testcase_03	AC	2 ms; 4,380 KB
testcase_04	AC	1 ms; 4,376 KB
testcase_05	AC	8 ms; 4,376 KB
testcase_06	AC	9 ms; 4,380 KB
testcase_07	AC	9 ms; 4,376 KB
testcase_08	AC	5 ms; 4,380 KB
testcase_09	AC	2 ms; 4,376 KB
testcase_10	AC	1 ms; 4,380 KB
testcase_11	AC	5 ms; 4,380 KB
testcase_12	AC	3 ms; 4,380 KB
testcase_13	AC	7 ms; 4,376 KB
testcase_14	AC	3 ms; 4,376 KB
testcase_15	AC	423 ms; 5,896 KB
testcase_16	AC	423 ms; 5,896 KB
testcase_17	AC	460 ms; 4,552 KB
testcase_18	AC	450 ms; 4,852 KB
testcase_19	AC	337 ms; 4,376 KB
testcase_20	AC	435 ms; 5,572 KB
testcase_21	AC	490 ms; 4,752 KB
testcase_22	AC	445 ms; 5,776 KB
testcase_23	AC	472 ms; 4,460 KB
testcase_24	AC	428 ms; 4,380 KB
testcase_25	AC	3 ms; 4,380 KB
testcase_26	AC	4 ms; 4,380 KB
testcase_27	AC	4 ms; 4,380 KB
testcase_28	AC	4 ms; 4,376 KB
testcase_29	AC	3 ms; 4,376 KB
testcase_30	AC	4 ms; 4,380 KB
testcase_31	AC	3 ms; 4,380 KB
testcase_32	AC	4 ms; 4,376 KB
testcase_33	AC	4 ms; 4,380 KB
testcase_34	AC	4 ms; 4,380 KB
testcase_35	AC	3 ms; 4,380 KB
testcase_36	AC	3 ms; 4,380 KB
testcase_37	AC	3 ms; 4,376 KB
testcase_38	AC	3 ms; 4,376 KB
testcase_39	AC	3 ms; 4,376 KB
testcase_40	AC	4 ms; 4,380 KB
testcase_41	AC	3 ms; 4,380 KB
testcase_42	AC	3 ms; 4,376 KB
testcase_43	AC	3 ms; 4,380 KB
testcase_44	AC	3 ms; 4,376 KB
testcase_45	AC	415 ms; 7,088 KB
testcase_46	AC	415 ms; 6,236 KB
testcase_47	AC	417 ms; 6,752 KB
testcase_48	AC	366 ms; 6,928 KB
testcase_49	AC	360 ms; 7,076 KB
testcase_50	AC	362 ms; 7,328 KB
testcase_51	AC	436 ms; 6,404 KB
testcase_52	AC	395 ms; 6,480 KB
testcase_53	AC	408 ms; 6,496 KB
testcase_54	AC	453 ms; 6,484 KB
testcase_55	AC	441 ms; 6,224 KB
testcase_56	AC	420 ms; 6,596 KB
testcase_57	AC	386 ms; 6,404 KB
testcase_58	AC	396 ms; 6,640 KB
testcase_59	AC	402 ms; 7,276 KB
testcase_60	AC	390 ms; 7,156 KB
testcase_61	AC	389 ms; 6,888 KB
testcase_62	AC	377 ms; 6,376 KB
testcase_63	AC	448 ms; 6,424 KB
testcase_64	AC	408 ms; 6,752 KB
testcase_65	AC	16 ms; 4,380 KB
testcase_66	AC	17 ms; 4,376 KB
testcase_67	AC	218 ms; 6,636 KB
testcase_68	AC	206 ms; 6,692 KB
testcase_69	AC	289 ms; 4,380 KB
testcase_70	AC	258 ms; 6,228 KB
testcase_71	AC	215 ms; 4,380 KB
testcase_72	AC	241 ms; 4,904 KB
testcase_73	AC	251 ms; 6,220 KB
testcase_74	AC	227 ms; 4,380 KB
testcase_75	AC	287 ms; 4,528 KB
testcase_76	AC	277 ms; 5,892 KB
testcase_77	AC	238 ms; 4,380 KB
testcase_78	AC	262 ms; 4,376 KB
testcase_79	AC	372 ms; 4,540 KB
testcase_80	AC	332 ms; 5,960 KB
testcase_81	AC	362 ms; 4,588 KB
testcase_82	AC	331 ms; 4,376 KB
testcase_83	AC	282 ms; 5,164 KB
testcase_84	AC	397 ms; 5,104 KB
testcase_85	AC	35 ms; 4,376 KB
testcase_86	AC	48 ms; 4,380 KB
testcase_87	AC	179 ms; 9,596 KB
testcase_88	AC	167 ms; 9,388 KB
testcase_89	AC	1 ms; 4,376 KB
testcase_90	AC	2 ms; 4,380 KB
testcase_91	AC	1 ms; 4,376 KB

ソースコード

/* #region Head */

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pll = pair<ll, ll>;
template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;
using vll = vc<ll>;
using vvll = vvc<ll>;
using vld = vc<ld>;
using vvld = vvc<ld>;
using vs = vc<string>;
using vvs = vvc<string>;
template <class T, class U> using um = unordered_map<T, U>;
template <class T> using pq = priority_queue<T>;
template <class T> using pqa = priority_queue<T, vc<T>, greater<T>>;
template <class T> using us = unordered_set<T>;

#define REP(i, m, n) for (ll i = (m), i##_len = (ll)(n); i < i##_len; ++(i))
#define REPM(i, m, n) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; ++(i))
#define REPR(i, m, n) for (ll i = (m), i##_min = (ll)(n); i >= i##_min; --(i))
#define REPD(i, m, n, d) for (ll i = (m), i##_len = (ll)(n); i < i##_len; i += (d))
#define REPMD(i, m, n, d) for (ll i = (m), i##_max = (ll)(n); i <= i##_max; i += (d))
#define REPI(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define ALL(x) begin(x), end(x)
#define SIZE(x) ((ll)(x).size())
#define PERM(c)                                                                                                        \
    sort(ALL(c));                                                                                                      \
    for (bool c##p = 1; c##p; c##p = next_permutation(ALL(c)))
#define UNIQ(v) v.erase(unique(ALL(v)), v.end());
#define CEIL(a, b) (((a) + (b)-1) / (b))

#define endl '\n'
#define sqrt sqrtl
#define floor floorl
#define log2 log2l

constexpr ll INF = 1'010'000'000'000'000'017LL;
constexpr int IINF = 1'000'000'007LL;
constexpr ll MOD = 1'000'000'007LL; // 1e9 + 7
// constexpr ll MOD = 998244353;
constexpr ld EPS = 1e-12;
constexpr ld PI = 3.14159265358979323846;

template <typename T> istream &operator>>(istream &is, vc<T> &vec) { // vector 入力
    for (T &x : vec) is >> x;
    return is;
}
template <typename T> ostream &operator<<(ostream &os, vc<T> &vec) { // vector 出力 (for dump)
    os << "{";
    REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "" : ", ");
    os << "}";
    return os;
}
template <typename T> ostream &operator>>(ostream &os, vc<T> &vec) { // vector 出力 (inline)
    REP(i, 0, SIZE(vec)) os << vec[i] << (i == i_len - 1 ? "\n" : " ");
    return os;
}

template <typename T, typename U> istream &operator>>(istream &is, pair<T, U> &pair_var) { // pair 入力
    is >> pair_var.first >> pair_var.second;
    return is;
}
template <typename T, typename U> ostream &operator<<(ostream &os, pair<T, U> &pair_var) { // pair 出力
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}

// map, um, set, us 出力
template <class T> ostream &out_iter(ostream &os, T &map_var) {
    os << "{";
    REPI(itr, map_var) {
        os << *itr;
        auto itrcp = itr;
        if (++itrcp != map_var.end()) os << ", ";
    }
    return os << "}";
}
template <typename T, typename U> ostream &operator<<(ostream &os, map<T, U> &map_var) { return out_iter(os, map_var); }
template <typename T, typename U> ostream &operator<<(ostream &os, um<T, U> &map_var) {
    os << "{";
    REPI(itr, map_var) {
        auto [key, value] = *itr;
        os << "(" << key << ", " << value << ")";
        auto itrcp = itr;
        if (++itrcp != map_var.end()) os << ", ";
    }
    os << "}";
    return os;
}
template <typename T> ostream &operator<<(ostream &os, set<T> &set_var) { return out_iter(os, set_var); }
template <typename T> ostream &operator<<(ostream &os, us<T> &set_var) { return out_iter(os, set_var); }
template <typename T> ostream &operator<<(ostream &os, pq<T> &pq_var) {
    pq<T> pq_cp(pq_var);
    os << "{";
    if (!pq_cp.empty()) {
        os << pq_cp.top(), pq_cp.pop();
        while (!pq_cp.empty()) os << ", " << pq_cp.top(), pq_cp.pop();
    }
    return os << "}";
}

void pprint() { cout << endl; }
template <class Head, class... Tail> void pprint(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(Tail) > 0) cout << ' ';
    pprint(move(tail)...);
}

// dump
#define DUMPOUT cerr
void dump_func() { DUMPOUT << endl; }
template <class Head, class... Tail> void dump_func(Head &&head, Tail &&... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) DUMPOUT << ", ";
    dump_func(move(tail)...);
}

// chmax (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>> bool chmax(T &xmax, const U &x, Comp comp = {}) {
    if (comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}

// chmin (更新「される」かもしれない値が前)
template <typename T, typename U, typename Comp = less<>> bool chmin(T &xmin, const U &x, Comp comp = {}) {
    if (comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

// ローカル用
#ifndef ONLINE_JUDGE
#define DEBUG_
#endif

#ifdef DEBUG_
#define DEB
#define dump(...)                                                                                                      \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                                                                    \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]" << endl                                        \
            << "    ",                                                                                                 \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif

#define VAR(type, ...)                                                                                                 \
    type __VA_ARGS__;                                                                                                  \
    cin >> __VA_ARGS__;

template <typename T> istream &operator,(istream &is, T &rhs) { return is >> rhs; }
template <typename T> ostream &operator,(ostream &os, const T &rhs) { return os << ' ' << rhs; }

struct AtCoderInitialize {
    static constexpr int IOS_PREC = 15;
    static constexpr bool AUTOFLUSH = false;
    AtCoderInitialize() {
        ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
        cout << fixed << setprecision(IOS_PREC);
        if (AUTOFLUSH) cout << unitbuf;
    }
} ATCODER_INITIALIZE;

void Yn(bool p) { cout << (p ? "Yes" : "No") << endl; }
void YN(bool p) { cout << (p ? "YES" : "NO") << endl; }

/* #endregion */

// #include <atcoder/all>
// using namespace atcoder;

/* #region RBST */

// https://ei1333.github.io/luzhiled/snippets/structure/rbst.html
// モノイド T と作用素 E
template <class T, class E = T> struct RandomizedBinarySearchTree {
    using F = function<T(T, T)>;
    using G = function<T(T, E)>;
    using H = function<E(E, E)>;
    using P = function<E(E, size_t)>;

    // 乱数生成 (xorshift)
    inline static uint32_t xor128() {
        static uint32_t x = 123456789;
        static uint32_t y = 362436069;
        static uint32_t z = 521288629;
        static uint32_t w = 88675123;
        uint32_t t;

        t = x ^ (x << 11);
        x = y;
        y = z;
        z = w;
        return w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    }

    // 木のノード
    struct Node {
        Node *l = nullptr, *r = nullptr;
        size_t cnt = 1ul;
        bool rev = false;
        T key, sum;
        E lazy;

        Node() = default;

        // 値 k を持つノードをつくる．作用素は p で初期化する．
        Node(const T &k, const E &p) : key(k), sum(k), lazy(p) {}
    };

    using NodePair = pair<Node *, Node *>;

    Node *root = nullptr; // 根
    const T ti;           // 要素の単位元，1 など．
    const E ei;           // 作用素の単位元，0 など．
    const F f;            // 要素と要素をマージする関数
    const G g;            // 要素に作用素を作用させる関数
    const H h;            // 作用素と作用素をマージする関数
    const P p; // 要素に作用素を作用させる前に，区間の長さを考慮して作用素を加工して返す関数．
               // (作用素, 区間長さ) ->加工済み作用素．

    /**
     * コンストラクタ．遅延伝播・区間アップデートを行わない場合はこちら．
     * @param sz ノード数
     * @param f 要素と要素をマージする関数
     * @param ti 要素の単位元
     */
    RandomizedBinarySearchTree(const F &f, const T &ti) : ti(ti), ei(E()), f(f), g(G()), h(H()), p(P()) {}

    /**
     * コンストラクタ．
     * @param f 要素と要素をマージする関数
     * @param g 要素に作用素を作用させる関数
     * @param h 作用素と作用素をマージする関数
     * @param p 要素に作用素を作用させる前に，区間の長さを考慮して作用素を加工して返す関数．
     *          (作用素, 区間長さ) -> 加工済み作用素．
     * @param ti 要素の単位元
     * @param ei 作用素の単位元
     */
    RandomizedBinarySearchTree(const F &f, const G &g, const H &h, const P &p, const T &ti, const E &ei)
        : ti(ti), ei(ei), f(f), g(g), h(h), p(p) {}

    // デストラクタ
    ~RandomizedBinarySearchTree() { sweep(root); }

  private:
    // 新しいノードを生成する
    inline Node *alloc(const T &key) { return new Node(key, ei); }

    virtual Node *clone(Node *t) { return t; }

    inline T sum(const Node *t) const { return t ? t->sum : ti; }

    // 子ノード再計算済み状態で，指定ノードの値を再計算する
    inline Node *recalc(Node *t) {
        t->cnt = count(t->l) + count(t->r) + 1ul;
        t->sum = f(f(sum(t->l), t->key), sum(t->r));
        return t;
    }

    // 遅延を子ノードへ伝播する
    Node *propagate(Node *t) {
        t = clone(t);
        if (t->lazy != ei) {
            t->key = g(t->key, p(t->lazy, 1));
            if (t->l) {
                t->l = clone(t->l);
                t->l->lazy = h(t->l->lazy, t->lazy);
                t->l->sum = g(t->l->sum, p(t->lazy, count(t->l)));
            }
            if (t->r) {
                t->r = clone(t->r);
                t->r->lazy = h(t->r->lazy, t->lazy);
                t->r->sum = g(t->r->sum, p(t->lazy, count(t->r)));
            }
            t->lazy = ei;
        }
        if (t->rev) {
            swap(t->l, t->r);
            if (t->l) t->l->rev ^= 1;
            if (t->r) t->r->rev ^= 1;
            t->rev = false;
        }
        return recalc(t);
    }

    // 木 l と木 r を併合する
    Node *merge(Node *l, Node *r) {
        if (!l || !r) return l ? l : r;
        if (xor128() % (l->cnt + r->cnt) < l->cnt) {
            l = propagate(l);
            l->r = merge(l->r, r);
            return recalc(l);
        } else {
            r = propagate(r);
            r->l = merge(l, r->l);
            return recalc(r);
        }
    }

    // 木 t を [0,k) [k,n) で分割する
    NodePair split(Node *t, size_t k) {
        if (!t) return {t, t};
        t = propagate(t);
        if (k <= count(t->l)) {
            NodePair s = split(t->l, k);
            t->l = s.second;
            return {s.first, recalc(t)};
        } else {
            NodePair s = split(t->r, k - count(t->l) - 1);
            t->r = s.first;
            return {recalc(t), s.second};
        }
    }

    Node *build(size_t l, size_t r, const vc<T> &v) {
        if (l + 1 >= r) return alloc(v[l]);
        return merge(build(l, (l + r) >> 1, v), build((l + r) >> 1, r, v));
    }

    // 木 t を再帰的に辿って，通りがけ順に値を配列に詰めていく
    void _dump(Node *t, typename vc<T>::iterator &it) {
        if (!t) return;
        t = propagate(t);
        _dump(t->l, it);
        *it = t->key;
        _dump(t->r, ++it);
    }

    // 木 t の各ノードを通りがけ順に格納したものを返す．O(n)．
    vc<T> _dump(Node *t) {
        vc<T> v(count(t));
        typename vc<T>::iterator it = begin(v);
        _dump(t, it);
        return v;
    }

    // 木 t の位置 k にノード v を挿入する
    void insert(Node *&t, size_t k, const T &v) {
        NodePair x = split(t, k);
        t = merge(merge(x.first, alloc(v)), x.second);
    }

    // k (0-indexed) 番目の要素を返す
    T kth_element(Node *t, size_t k) const {
        assert(k < count(t));
        if (k < count(t->l)) return kth_element(t->l, k);
        if (k == count(t->l)) return t->key;
        return kth_element(t->r, k - count(t->l) - 1);
    }

    // 木 t の位置 k のノードを削除する
    void erase(Node *&t, size_t k) {
        NodePair x = split(t, k);
        NodePair y = split(x.second, 1);
        delete y.first;
        t = merge(x.first, y.second);
    }

    // 木を再帰的に消していく
    void sweep(Node *r) const {
        if (r == nullptr) return;
        if (r->l != nullptr) {
            sweep(r->l);
            r->l = nullptr;
        }
        if (r->r != nullptr) {
            sweep(r->r);
            r->r = nullptr;
        }
        delete r;
    }

    // 木 t の区間 [a, b) の値を二項演算した結果を返す
    T query(Node *&t, size_t a, size_t b) {
        // assert(b > a);
        if (a >= b) return ti;
        NodePair x = split(t, a);            // 区間始点で左右に分割
        NodePair y = split(x.second, b - a); // 必要個数分切り出せるように分割
        T ret = sum(y.first);
        t = merge(x.first, merge(y.first, y.second));
        return ret;
    }

    // 木 t の区間 [a, b) に作用素 p を適用する
    void update(Node *&t, size_t a, size_t b, const E &p) {
        // assert(b > a);
        if (a >= b) return;
        NodePair x = split(t, a);            // 区間始点で左右に分割
        NodePair y = split(x.second, b - a); // 必要個数分切り出せるように分割
        y.first->lazy = h(y.first->lazy, p);
        t = merge(x.first, merge(propagate(y.first), y.second));
    }

    // 木 t の区間 [a, b) を左右反転する
    void reverse(Node *&t, int a, int b) {
        assert(b > a);
        NodePair x = split(t, a);            // 区間始点で左右に分割
        NodePair y = split(x.second, b - a); // 必要個数分切り出せるように分割
        if (y.first) y.first->rev ^= 1;
        t = merge(x.first, merge(y.first, y.second));
    }

    // 木 t の区間 [a, b) に対して c 個ぶんの巡回シフト（右にズレる方向）をかける
    void circular_shift(Node *&t, int a, int b, int c) {
        assert(b > a);
        if (c == 0) return;
        if (c > 0) { // 右シフト
            c %= (b - a);
            if (c == 0) return;
            NodePair x = split(t, a);               // 区間始点で左右に分割
            NodePair y = split(x.second, b - a);    // 必要個数分切り出せるように分割
            NodePair z = split(y.first, b - a - c); // シフトで分割されるところで切る
            t = merge(x.first, merge(merge(z.second, z.first), y.second));
        } else { // 左シフト
            c *= -1;
            c %= (b - a);
            if (c == 0) return;
            NodePair x = split(t, a);            // 区間始点で左右に分割
            NodePair y = split(x.second, b - a); // 必要個数分切り出せるように分割
            NodePair z = split(y.first, c);      // シフトで分割されるところで切る
            t = merge(x.first, merge(merge(z.second, z.first), y.second));
        }
    }

    // 木 t の k (0-indexed) 番目の値を x に変更する
    void set_val(Node *&t, size_t k, const T &x) {
        t = propagate(t);
        if (k < count(t->l))
            set_val(t->l, k, x);
        else if (k == count(t->l))
            t->key = t->sum = x;
        else
            set_val(t->r, k - count(t->l) - 1, x);
        t = recalc(t);
    }

    // 木 t が空木かどうかを返す
    static bool empty(Node *t) { return !t; }

  protected:
    // 木 t のノード数を返す
    inline static size_t count(const Node *t) { return t ? t->cnt : 0ul; }

  public:
    // 木 root のノード数を返す
    size_t size() const { return count(root); }

    // ベクトル v をもとに木を構築する．O(n)．
    void build(const vc<T> &v) {
        // ptr = 0;
        root = build(0ul, v.size(), v);
    }

    // 木 root の位置 k にノード v を挿入する
    void insert(size_t k, const T &v) {
        NodePair x = split(root, k);
        root = merge(merge(x.first, alloc(v)), x.second);
    }

    // 木 root の k (0-indexed) 番目の要素を返す
    T kth_element(size_t k) const { return kth_element(this->root, k); }

    // 木 root の位置 k のノードを削除する
    void erase(size_t k) {
        NodePair x = split(root, k);
        NodePair y = split(x.second, 1);
        delete y.first;
        root = merge(x.first, y.second);
    }

    // 木 root の区間 [a, b) の値を二項演算した結果を返す
    T query(size_t a, size_t b) { return query(root, a, b); }

    // 木 root の区間 [a, b) に作用素 p を適用する
    void update(size_t a, size_t b, const E &p) { update(root, a, b, p); }

    // 木 root の区間 [a, b) を左右反転する
    void reverse(int a, int b) { reverse(root, a, b); }

    // 木 t の区間 [a, b) に対して c 個ぶんの巡回シフト（右にズレる方向）をかける
    void circular_shift(int a, int b, int c) { circular_shift(root, a, b, c); }

    // 木 root の k (0-indexed) 番目の値を x に変更する
    void set_val(size_t k, const T &x) { set_val(root, k, x); }

    // 木 root が空木かどうかを返す
    bool empty() { return empty(root); }

    // 木 root の各ノードを通りがけ順に格納したものを返す．O(n)．
    vc<T> _dump() { return _dump(root); }
};

/* #endregion */

/* #region OrderedSet */

// k 番目が取れる多重集合（昇順ソート済みベクトルとして扱える）
template <class T, class E = T> struct OrderedMultiSet : RandomizedBinarySearchTree<T, E> {
    using RBST = RandomizedBinarySearchTree<T, E>;
    using Node = typename RBST::Node;
    using F = function<T(T, T)>;
    using G = function<T(T, E)>;
    using H = function<E(E, E)>;
    using P = function<E(E, size_t)>;

    // コンストラクタ
    OrderedMultiSet() : RBST([](T x, [[maybe_unused]] T y) -> T { return x; }, T()) {}
    // コンストラクタ
    OrderedMultiSet(const F &f, const G &g, const H &h, const P &p, const T &ti, const E &ei)
        : RBST(f, g, h, p, ti, ei) {}

    // 多重集合のサイズを返す
    size_t size() const { return RBST::size(); }

    // 多重集合に値 x を挿入する
    virtual void insert(const T &x) { RBST::insert(lower_bound(x), x); }

    // 多重集合から値 x を削除する
    void erase(const T &x) {
        if (!count(x)) return;
        RBST::erase(lower_bound(this->root, x));
    }

    void erase_kth_element(const size_t k) {
        assert(k < size());
        RBST::erase(k);
    }

    // 多重集合に含まれる値 x の個数を返す
    size_t count(const T &x) const { return count(this->root, x); }

    // x 以上の最小の要素のインデックスを返す
    size_t lower_bound(const T &x) const { return lower_bound(this->root, x); }

    // x より大きい最小の要素のインデックスを返す
    size_t upper_bound(const T &x) const { return upper_bound(this->root, x); }

  private:
    // 木 t に含まれる値 x の個数を返す
    size_t count(Node *t, const T &x) const { return upper_bound(t, x) - lower_bound(t, x); }

    // 木 t に含まれる x 以上の最小の要素のインデックスを返す
    size_t lower_bound(Node *t, const T &x) const {
        if (!t) return 0ul;
        if (x <= t->key) return lower_bound(t->l, x);
        return lower_bound(t->r, x) + RBST::count(t->l) + 1ul;
    }

    // 木 t に含まれる x より大きい最小の要素のインデックスを返す
    size_t upper_bound(Node *t, const T &x) const {
        if (!t) return 0ul;
        if (x < t->key) return upper_bound(t->l, x);
        return upper_bound(t->r, x) + RBST::count(t->l) + 1ul;
    }
};

// 1 種類の値は1つのみ格納する通常の集合，k 番目が取れるようになったもの
template <class T> struct OrderedSet : OrderedMultiSet<T> {
    using SET = OrderedMultiSet<T>;
    using RBST = typename SET::RBST;
    using Node = typename RBST::Node;

    OrderedSet() : OrderedMultiSet<T>() {}

    // 集合に値 x を挿入する．既に値 x が存在する場合は何もしない．
    void insert(const T &x) override {
        if (SET::count(x)) return;
        RBST::insert(SET::lower_bound(x), x);
    }
};

/* #endregion */

// Problem
void solve() {
    VAR(ll, n, k);
    vll a(n);
    cin >> a;

    using F = function<ll(ll, ll)>;
    using P = function<ll(ll, size_t)>;
    F f = [](ll a, ll b) -> ll { return a + b; }; // 要素のマージ
    P p = [](ll a, size_t b) -> ll { return a * b; };

    OrderedMultiSet<ll> st(f, f, f, p, 0, 0);

    REP(i, 0, k - 1) st.insert(a[i]);

    ll mi = INF;
    REPM(r, k, n) {
        st.insert(a[r - 1]);
        ll l = r - k;
        ll m = (k - 1) / 2;
        ll median = st.kth_element((k - 1) / 2);
        ll sum_l = st.query(0, m);
        ll sum_r = st.query(m + 1, k);
        ll cost_l = median * (m - 0) - sum_l;
        ll cost_r = sum_r - median * (k - (m + 1));
        ll cost = cost_l + cost_r;
        chmin(mi, cost);
        st.erase(a[l]);
    }

    pprint(mi);
}

// entry point
int main() {
    solve();
    return 0;
}