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

提出ソース

結果

問題	No.738 平らな農地
ユーザー	micheeeeell1001
提出日時	2020-09-05 03:07:34
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,089 ms / 2,000 ms
コード長	19,548 bytes
コンパイル時間	3,538 ms
コンパイル使用メモリ	240,644 KB
実行使用メモリ	40,024 KB
最終ジャッジ日時	2024-05-05 08:40:58
合計ジャッジ時間	41,914 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 5,248 KB
testcase_01	AC	2 ms 5,376 KB
testcase_02	AC	2 ms 5,376 KB
testcase_03	AC	2 ms 5,376 KB
testcase_04	AC	2 ms 5,376 KB
testcase_05	AC	26 ms 5,376 KB
testcase_06	AC	33 ms 5,376 KB
testcase_07	AC	19 ms 5,376 KB
testcase_08	AC	11 ms 5,376 KB
testcase_09	AC	6 ms 5,376 KB
testcase_10	AC	3 ms 5,376 KB
testcase_11	AC	11 ms 5,376 KB
testcase_12	AC	7 ms 5,376 KB
testcase_13	AC	23 ms 5,376 KB
testcase_14	AC	9 ms 5,376 KB
testcase_15	AC	597 ms 33,420 KB
testcase_16	AC	618 ms 33,952 KB
testcase_17	AC	776 ms 33,820 KB
testcase_18	AC	739 ms 33,416 KB
testcase_19	AC	959 ms 35,536 KB
testcase_20	AC	624 ms 34,076 KB
testcase_21	AC	864 ms 35,664 KB
testcase_22	AC	667 ms 34,204 KB
testcase_23	AC	856 ms 34,864 KB
testcase_24	AC	885 ms 34,344 KB
testcase_25	AC	7 ms 5,376 KB
testcase_26	AC	7 ms 5,376 KB
testcase_27	AC	8 ms 5,376 KB
testcase_28	AC	7 ms 5,376 KB
testcase_29	AC	8 ms 5,376 KB
testcase_30	AC	7 ms 5,376 KB
testcase_31	AC	7 ms 5,376 KB
testcase_32	AC	6 ms 5,376 KB
testcase_33	AC	7 ms 5,376 KB
testcase_34	AC	6 ms 5,376 KB
testcase_35	AC	6 ms 5,376 KB
testcase_36	AC	7 ms 5,376 KB
testcase_37	AC	6 ms 5,376 KB
testcase_38	AC	8 ms 5,376 KB
testcase_39	AC	8 ms 5,376 KB
testcase_40	AC	7 ms 5,376 KB
testcase_41	AC	8 ms 5,376 KB
testcase_42	AC	6 ms 5,376 KB
testcase_43	AC	6 ms 5,376 KB
testcase_44	AC	7 ms 5,376 KB
testcase_45	AC	547 ms 36,580 KB
testcase_46	AC	574 ms 34,056 KB
testcase_47	AC	538 ms 35,652 KB
testcase_48	AC	458 ms 34,464 KB
testcase_49	AC	459 ms 34,328 KB
testcase_50	AC	464 ms 35,648 KB
testcase_51	AC	612 ms 35,780 KB
testcase_52	AC	529 ms 34,332 KB
testcase_53	AC	570 ms 34,988 KB
testcase_54	AC	587 ms 35,912 KB
testcase_55	AC	623 ms 35,780 KB
testcase_56	AC	582 ms 35,388 KB
testcase_57	AC	524 ms 33,788 KB
testcase_58	AC	539 ms 35,252 KB
testcase_59	AC	530 ms 36,828 KB
testcase_60	AC	487 ms 36,440 KB
testcase_61	AC	509 ms 36,172 KB
testcase_62	AC	507 ms 33,808 KB
testcase_63	AC	621 ms 36,704 KB
testcase_64	AC	557 ms 36,300 KB
testcase_65	AC	974 ms 34,080 KB
testcase_66	AC	993 ms 35,128 KB
testcase_67	AC	597 ms 37,644 KB
testcase_68	AC	587 ms 38,568 KB
testcase_69	AC	974 ms 38,844 KB
testcase_70	AC	733 ms 39,768 KB
testcase_71	AC	42 ms 8,076 KB
testcase_72	AC	616 ms 29,964 KB
testcase_73	AC	504 ms 28,104 KB
testcase_74	AC	825 ms 31,164 KB
testcase_75	AC	876 ms 37,512 KB
testcase_76	AC	671 ms 38,440 KB
testcase_77	AC	972 ms 37,516 KB
testcase_78	AC	1,041 ms 39,900 KB
testcase_79	AC	995 ms 39,896 KB
testcase_80	AC	715 ms 38,704 KB
testcase_81	AC	879 ms 38,040 KB
testcase_82	AC	976 ms 39,356 KB
testcase_83	AC	720 ms 32,096 KB
testcase_84	AC	630 ms 31,428 KB
testcase_85	AC	1,089 ms 40,024 KB
testcase_86	AC	957 ms 37,768 KB
testcase_87	AC	118 ms 39,088 KB
testcase_88	AC	112 ms 37,896 KB
testcase_89	AC	2 ms 5,376 KB
testcase_90	AC	2 ms 5,376 KB
testcase_91	AC	2 ms 5,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(ll i = (ll)(s); i < (ll)(t); i++)
#define rrep(i,s,t) for(ll i = (ll)(s-1);(ll)(t) <= i; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
constexpr ll INF = numeric_limits<ll>::max()/4;
constexpr ll n_max = 2e5+10;
#define int ll

template <typename A, typename B>
string to_string(pair<A, B> p);
string to_string(const string &s) {return '"' + s + '"';}
string to_string(const char *c) {return to_string((string) c);}
string to_string(bool b) {return (b ? "true" : "false");}
template <size_t N>
string to_string(bitset<N> v){
    string res = "";
    for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);
    return res;
}
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}

void debug_out() {cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

template<class T>
bool chmax(T &a, T b){if(a < b){a = b; return true;} return false;}
template<class T>
bool chmin(T &a, T b){if(a > b){a = b; return true;} return false;}

using u16 = unsigned short;
using u32 = unsigned;
struct bitVector {
    u32 length, cnum, bnum;  // bit列の長さ、chunk数、chunkごとのblock数

    u16 bw = 16, cw = 1024;  // chunk, blockの大きさ
    vector<u16> bit;         //元データ
    vector<u32> chunk;
    vector<vector<u16>> block;

    bitVector(int N) : length(N) {
        cnum = (N + cw - 1) / cw;
        bnum = cw / bw;

        bit.assign(cnum * bnum, 0);
        chunk.assign(cnum + 1, 0);
        block.assign(cnum, vector<u16>(bnum, 0));
    }

    void set(int pos, int b) {
        int bpos = pos / bw;
        int offset = pos % bw;

        if(b == 0) {
            bit[bpos] &= ~(1 << offset);
        } else if(b == 1) {
            bit[bpos] |= (1 << offset);
        }
    }

    void build() {
        int pos = 0;
        int sum = 0, bsum = 0;
        for(int i = 0; i < cnum; i++) {
            bsum = 0;
            for(int j = 1; j < bnum; j++) {
                bsum += __builtin_popcount(bit[pos++]);
                block[i][j] = bsum;
            }
            sum += bsum + __builtin_popcount(bit[pos++]);
            chunk[i + 1] = sum;
        }
    }

    int access(int pos) {
        int bpos = pos / bw;
        int offset = pos % bw;
        return (bit[bpos] >> offset) & 1;
    }

    // [0, pos)に含まれるbの数を返す
    int rank(int pos, int b) {
        int cpos = pos / cw;
        int bpos = (pos % cw) / bw;
        int offset = pos % bw;
        u16 mask = bit[cpos * bnum + bpos] & ((1 << offset) - 1);
        int res = chunk[cpos] + block[cpos][bpos] + __builtin_popcount(mask);

        return b == 1 ? res : pos - res;
    }

    // [l, r)に含まれる1の数を返す
    int rank(int l, int r, int b) {
        return rank(r, b) - rank(l, b);
    }

    // rank(idx, b) = numなる最小のidxを返す
    // つまり、num番目のbの位置(1-indexed)を返す
    int select(int num, int b) {
        if(rank(length, b) < num) return -1;

        int ok = length;
        int ng = -1;
        while(ok - ng > 1) {
            int x = (ok + ng) / 2;
            if(rank(x, b) >= num)
                ok = x;
            else
                ng = x;
        }

        return ok;
    }
};

template <typename T>
struct WaveletMatrix {
    int LOG;
    T max_;
    vector<bitVector> bv;
    int n;
    vector<int> border;
    unordered_map<T, int> first_id, count;
    vector< vector<T> > cumulative_sum;

    WaveletMatrix(int n, vector<T> &v) : n(n) {
        max_ = *max_element(v.begin(), v.end()) + 1;
        LOG = get_num_of_bit(max_);
        bv.assign(LOG, bitVector(n));
        border.resize(LOG);
        cumulative_sum.resize(LOG + 1, vector<T>(n + 1, 0));
        build(v);
    }

    void build(vector<T> &v) {
        vector<T> pre, suf, vec = v;
        for(int i = 0; i < n; i++){
            cumulative_sum[0][i+1] = cumulative_sum[0][i] + vec[i];
        }

        for(int i = 0; i < LOG; i++) {
            for(int j = 0; j < n; j++) {
                if((vec[j] >> (LOG - i - 1)) & 1) {
                    suf.emplace_back(vec[j]);
                    bv[i].set(j, 1);
                } else {
                    pre.emplace_back(vec[j]);
                    bv[i].set(j, 0);
                }
            }
            border[i] = pre.size();
            int id = 0;
            for(auto &a : pre) vec[id++] = a;
            for(auto &a : suf) vec[id++] = a;
            for(int j = 0; j < n; j++){
                cumulative_sum[i+1][j+1] = cumulative_sum[i+1][j] + vec[j];
            }
            pre.clear();
            suf.clear();
            bv[i].build();
        }
        for(int i = 0; i < n; i++) {
            count[vec[i]]++;
            if(first_id.count(vec[i])) continue;
            first_id[vec[i]] = i;
        }
    }

    // idx番目の数
    T access(int idx) {
        T res = 0;
        T tmp;
        for(int i = 0; i < LOG; i++) {
            tmp = bv[i].access(idx);
            res |= (T)tmp << (LOG - i - 1);
            idx = bv[i].rank(idx, tmp);
            idx += (tmp == 1 ? border[i] : 0);
        }
        return res;
    }

    // [0, idx)に数値cが現れた回数
    int rank(int idx, T c) {
        if(!first_id.count(c)) return 0;
        int tmp = 0;
        for(int i = 0; i < LOG; i++) {
            tmp = c >> (LOG - i - 1) & 1;
            idx = bv[i].rank(idx, tmp);
            idx += (tmp == 1 ? border[i] : 0);
        }
        return idx - first_id[c];
    }
    // [l, r)に数値cが現れた回数
    int rank(int l, int r, T c) {
        return rank(r, c) - rank(l, c);
    }

    // 前からnum番目のcのidx(1-indexed)（無いときは-1）
    int select(int num, T c) {
        if(num == 0 || !first_id.count(c) || count[c] < num) {
            return -1;
        }
        int idx = first_id[c] + num;
        int tmp = 0;
        for(int i = LOG - 1; 0 <= i; i--) {
            tmp = c >> (LOG - i - 1) & 1;
            idx = bv[i].select((tmp ? idx - border[i] : idx), tmp);
        }

        return idx;
    }

    // [l, r)の中でnum番目に小さい値
    T quantile(int l, int r, int num) {
        assert(r > l && num <= r - l);
        int tmp, cnt0, cnt1;
        T res = 0;
        for(int i = 0; i < LOG; i++) {
            cnt0 = bv[i].rank(l, r, 0);
            cnt1 = r - l - cnt0;
            tmp = (num <= cnt0 ? 0 : 1);
            l = bv[i].rank(l, tmp);
            r = bv[i].rank(r, tmp);
            if(tmp) {
                l += border[i];
                r += border[i];
                num -= cnt0;
            }
            res |= (T)tmp << (LOG - i - 1);
            // debug(l, r, cnt0, cnt1, tmp);
        }
        return res;
    }

    // [l, r)の中で出現頻度の高い順にk個の(値、出現回数)を返す
    vector<pair<T, int>> topk(int l, int r, int k) {
        vector<pair<T, int>> res;
        // 順に頻度、左端、深さ、値
        using tp = tuple<int, int, int, T>;

        auto comp = [](const tp &l, const tp &r) {
            if(get<0>(l) != get<0>(r)) {
                return get<0>(l) < get<0>(r);
            }
            if(get<2>(l) != get<2>(r)) {
                return get<2>(l) > get<2>(r);
            }
            return get<3>(l) < get<3>(r);
        };

        priority_queue<tp, vector<tp>, decltype(comp)> pq(comp);
        pq.emplace(r - l, l, 0, 0);
        while(!pq.empty()) {
            auto [width, l, depth, value] = pq.top();
            pq.pop();
            if(depth == LOG) {
                res.emplace_back(value, width);
                if(res.size() >= k) {
                    break;
                }
            } else {
                int cnt, l2;
                for(int i = 0; i < 2; i++) {
                    cnt = bv[depth].rank(l, l + width, i);
                    if(!cnt) continue;
                    l2 = bv[depth].rank(l, i);
                    if(i) l2 += border[depth];
                    pq.emplace(cnt, l2, depth + 1,
                               value | ((T)i << (LOG - depth - 1)));
                }
            }
        }

        return res;
    }

    // [l, r)の中に出現する値を大きい順にk個、頻度とともに列挙
    vector<pair<T, int>> rangeMaxk(int l, int r, int k) {
        using tp = tuple<int, int, int, T>;
        vector<tp> v;
        v.emplace_back(0, l, r, 0);
        vector<pair<T, int>> res;

        int tmp, l0, r0, l1, r1;
        while(!v.empty()) {
            auto [depth, left, right, value] = v.back();
            v.pop_back();

            if(depth == LOG) {
                res.emplace_back(value, right - left);
                if(res.size() >= k) break;
                continue;
            }

            l0 = bv[depth].rank(left, 0);
            r0 = bv[depth].rank(right, 0);
            l1 = left - l0 + border[depth];
            r1 = right - r0 + border[depth];

            if(r0 - l0) {
                v.emplace_back(depth + 1, l0, r0, value);
            }

            if(r1 - l1) {
                v.emplace_back(depth + 1, l1, r1,
                               value | ((T)1 << (LOG - depth - 1)));
            }
        }

        return res;
    }
    // [l, r)の中に出現する値を小さい順にk個、頻度とともに列挙
    vector<pair<T, int>> rangeMink(int l, int r, int k) {
        using tp = tuple<int, int, int, T>;
        vector<tp> v;
        v.emplace_back(0, l, r, 0);
        vector<pair<T, int>> res;

        int tmp, l0, r0, l1, r1;
        while(!v.empty()) {
            auto [depth, left, right, value] = v.back();
            v.pop_back();

            if(depth == LOG) {
                res.emplace_back(value, right - left);
                if(res.size() >= k) break;
                continue;
            }

            l0 = bv[depth].rank(left, 0);
            r0 = bv[depth].rank(right, 0);
            l1 = left - l0 + border[depth];
            r1 = right - r0 + border[depth];

            if(r1 - l1) {
                v.emplace_back(depth + 1, l1, r1,
                               value | ((T)1 << (LOG - depth - 1)));
            }
            if(r0 - l0) {
                v.emplace_back(depth + 1, l0, r0, value);
            }
        }

        return res;
    }

    // [l, r)においてx <= c < yを満たすcの値と出現頻度を列挙
    vector<pair<T, int>> rangeList(int l, int r, T x, T y) {
        if(x >= y || l >= r || y == 0 || r == 0) {
            return {};
        }
        using tp = tuple<int, int, int, int, T>;
        vector<tp> v;
        vector<pair<T, int>> res;
        y--;  // x <= c <= y
        v.emplace_back(0, l, r, 0, 0);

        int tmp, l0, l1, r0, r1;
        while(!v.empty()) {
            auto [depth, left, right, is_small, value] = v.back();
            // debug(depth, left, right, is_small, value);
            v.pop_back();
            if(depth == LOG) {
                if(value >= x) {
                    res.emplace_back(value, right - left);
                }
            } else {
                tmp = y >> (LOG - depth - 1) & 1;

                l0 = bv[depth].rank(left, 0);
                r0 = bv[depth].rank(right, 0);
                l1 = left - l0 + border[depth];
                r1 = right - r0 + border[depth];

                if(r0 - l0) {
                    v.emplace_back(depth + 1, l0, r0, is_small | (tmp == 1),
                                   value);
                }

                if(is_small || tmp == 1) {
                    if(r1 - l1) {
                        v.emplace_back(depth + 1, l1, r1, is_small,
                                       value | ((T)1 << (LOG - depth - 1)));
                    }
                }
            }
        }

        return res;
    }

    // [l, r)の値の合計
    T rangeSum(int l, int r) {
        assert(r > l);
        auto v = rangeMaxk(l, r, r - l);
        T res = 0;
        for(auto &[val, freq] : v) {
            res += val * (T)freq;
        }
        return res;
    }

    // T rangeSum(int l, int r, T x, T y){
    //     auto v = rangeList(l, r, x, y);
    //     T res = 0;
    //     for(auto &[val, freq] : v){
    //         res += val * freq;
    //     }
    //     return res;
    // }

    T rangeSum(int l, int r, T x, T y){
        return rangeSum(l, r, 0, 0, x, y);
    }

    T rangeSum(int l, int r, int depth, T c, T x, T y){
        if(l == r)return 0;
        if(depth == LOG){
            if(x <= c && c < y){
                return c * (r - l);
            }
            return 0;
        }

        T next_c = (T)1 << (LOG - depth - 1) | c;
        T all_one_c = (((T)1 << (LOG - depth - 1)) - 1) | next_c;
        if(all_one_c < x || y <= c){
            return 0;
        }

        if(x <= c && all_one_c < y){
            return cumulative_sum[depth][r] - cumulative_sum[depth][l];
        }

        int l0 = bv[depth].rank(l, 0);
        int r0 = bv[depth].rank(r, 0);
        int l1 = l - l0 + border[depth];
        int r1 = r - r0 + border[depth];

        return rangeSum(l0, r0, depth+1, c, x, y) + rangeSum(l1, r1, depth+1, next_c, x, y);
    }

    // [l, r)でxより小さい数の出現回数
    int rangeFreq(int l, int r, T x) {
        int res = 0;
        T tmp;
        int cnt;
        for(int i = 0; i < LOG; i++) {
            tmp = x >> (LOG - i - 1) & 1;
            cnt = bv[i].rank(l, r, 0);
            l = bv[i].rank(l, tmp);
            r = bv[i].rank(r, tmp);
            if(tmp) {
                res += cnt;
                l += border[i];
                r += border[i];
            }
        }
        return res;
    }
    // [l, r)で x <= c < yを満たすcの出現回数
    int rangeFreq(int l, int r, T x, T y) {
        return rangeFreq(l, r, y) - rangeFreq(l, r, x);
    }

    // [l, r)で（cと同じ値の数、cより小さい値の数、cより大きい値のか数）
    tuple<int, int, int> rankAll(int l, int r, T c) {
        int num = r - l;

        int rank_less = 0, rank_more = 0;
        int tmp, l0, l1, r0, r1;
        for(int i = 0; i < LOG; i++) {
            tmp = c >> (LOG - i - 1) & 1;

            l0 = bv[i].rank(l, 0);
            r0 = bv[i].rank(r, 0);
            l1 = l - l0;
            r1 = r - r0;

            if(tmp) {
                rank_less += (r0 - l0);
                l = l1 + border[i];
                r = r1 + border[i];
            } else {
                rank_more += (r1 - l1);
                l = l0;
                r = r0;
            }
        }

        int rank = num - rank_less - rank_more;
        return make_tuple(rank, rank_less, rank_more);
    }

    int rankLess(int l, int r, T c) {
        auto t = rankAll(l, r, c);
        return get<1>(t);
    }
    int rankMore(int l, int r, T c) {
        auto t = rankAll(l, r, c);
        return get<2>(t);
    }

    // [l, r)でx <= c < yを満たす数の内、最大のもの
    T prevValue(int l, int r, T x, T y) {
        if(x >= y || l >= r || y == 0 || r == 0) {
            return -1;
        }
        using tp = tuple<int, int, int, int, T>;
        vector<tp> v;
        y--;  // x <= c <= y
        v.emplace_back(0, l, r, 0, 0);

        int tmp, l0, l1, r0, r1;
        while(!v.empty()) {
            auto [depth, left, right, is_small, value] = v.back();
            // debug(depth, left, right, is_small, value);
            v.pop_back();
            if(depth == LOG) {
                if(value >= x) {
                    return value;
                }
            } else {
                tmp = y >> (LOG - depth - 1) & 1;

                l0 = bv[depth].rank(left, 0);
                r0 = bv[depth].rank(right, 0);
                l1 = left - l0 + border[depth];
                r1 = right - r0 + border[depth];

                if(r0 - l0) {
                    v.emplace_back(depth + 1, l0, r0, is_small | (tmp == 1),
                                   value);
                }

                if(is_small || tmp == 1) {
                    if(r1 - l1) {
                        v.emplace_back(depth + 1, l1, r1, is_small,
                                       value | ((T)1 << (LOG - depth - 1)));
                    }
                }
            }
        }

        return -1;
    }

    // [l, r)でx <= c < yを満たす数の内、最小のもの
    T nextValue(int l, int r, T x, T y) {
        if(x >= y || l >= r || y == 0 || r == 0) {
            return -1;
        }
        using tp = tuple<int, int, int, int, T>;
        vector<tp> v;

        v.emplace_back(0, l, r, 0, 0);

        int tmp, l0, r0, l1, r1;
        while(!v.empty()) {
            auto [depth, left, right, is_large, value] = v.back();
            v.pop_back();
            if(depth == LOG) {
                if(value < y) {
                    return value;
                }
            }

            tmp = x >> (LOG - depth - 1) & 1;
            l0 = bv[depth].rank(left, 0);
            r0 = bv[depth].rank(right, 0);
            l1 = left - l0 + border[depth];
            r1 = right - r0 + border[depth];

            if(r1 - l1) {
                v.emplace_back(depth + 1, l1, r1, is_large | (tmp == 0),
                               value | ((T)1 << (LOG - depth - 1)));
            }

            if(is_large || tmp == 0) {
                if(r0 - l0) {
                    v.emplace_back(depth + 1, l0, r0, is_large, value);
                }
            }
        }

        return -1;
    }

    int get_num_of_bit(T x) {
        if(x == 0) return 0;
        x--;
        uint64_t bit_num = 0;
        while(x >> bit_num) {
            ++bit_num;
        }
        return bit_num;
    }
};
void print() {
    cout << endl;
}

template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
    cout << head;
    if (sizeof...(tail) != 0) cout << " ";
    print(forward<Tail>(tail)...);
}

template <class T>
void print(vector<T> &vec) {
    for (auto& a : vec) {
        cout << a;
        if (&a != &vec.back()) cout << " ";
    }
    cout << endl;
}

template <class T>
void print(vector<vector<T>> &df) {
    for (auto& vec : df) {
        print(vec);
    }
}

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    ll n,k; cin >> n >> k;
    vector<ll> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    WaveletMatrix<ll> wm(n, a);
    ll ans = INF;
    rep(i,0,n-k+1){
        ll m = 0;
        m = wm.quantile(i, i + k, (k + 1) / 2);
        ll tmp = 0;
        ll less_freq = wm.rangeFreq(i, i+k, 0, m), more_freq = k - less_freq;
        ll less_sum = wm.rangeSum(i, i+k, 0, m), more_sum = wm.rangeSum(i, i+k, m, INF);
        tmp = less_freq * m - less_sum + more_sum - m * more_freq;
        debug(i, m, tmp, less_freq, less_sum, more_freq, more_sum);
        chmin(ans, tmp);
    }

    cout << ans << endl;
}

yukicoder

結果

テストケース

ソースコード