結果

問題 No.738 平らな農地
ユーザー sonotarousonotarou
提出日時 2022-09-20 20:28:05
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 577 ms / 2,000 ms
コード長 5,521 bytes
コンパイル時間 2,866 ms
コンパイル使用メモリ 227,016 KB
実行使用メモリ 29,616 KB
最終ジャッジ日時 2024-06-01 17:03:00
合計ジャッジ時間 25,689 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,816 KB
testcase_02 AC 2 ms
6,812 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 2 ms
6,816 KB
testcase_05 AC 13 ms
6,944 KB
testcase_06 AC 15 ms
6,940 KB
testcase_07 AC 10 ms
6,944 KB
testcase_08 AC 6 ms
6,944 KB
testcase_09 AC 4 ms
6,940 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 6 ms
6,940 KB
testcase_12 AC 4 ms
6,944 KB
testcase_13 AC 12 ms
6,940 KB
testcase_14 AC 5 ms
6,940 KB
testcase_15 AC 291 ms
27,144 KB
testcase_16 AC 294 ms
27,520 KB
testcase_17 AC 376 ms
27,396 KB
testcase_18 AC 358 ms
26,880 KB
testcase_19 AC 456 ms
29,056 KB
testcase_20 AC 304 ms
27,648 KB
testcase_21 AC 410 ms
29,216 KB
testcase_22 AC 320 ms
27,652 KB
testcase_23 AC 409 ms
28,304 KB
testcase_24 AC 422 ms
27,784 KB
testcase_25 AC 4 ms
6,944 KB
testcase_26 AC 4 ms
6,940 KB
testcase_27 AC 4 ms
6,940 KB
testcase_28 AC 5 ms
6,940 KB
testcase_29 AC 5 ms
6,940 KB
testcase_30 AC 4 ms
6,940 KB
testcase_31 AC 4 ms
6,944 KB
testcase_32 AC 4 ms
6,940 KB
testcase_33 AC 5 ms
6,940 KB
testcase_34 AC 4 ms
6,940 KB
testcase_35 AC 4 ms
6,944 KB
testcase_36 AC 4 ms
6,940 KB
testcase_37 AC 4 ms
6,940 KB
testcase_38 AC 4 ms
6,944 KB
testcase_39 AC 5 ms
6,944 KB
testcase_40 AC 5 ms
6,944 KB
testcase_41 AC 5 ms
6,940 KB
testcase_42 AC 4 ms
6,944 KB
testcase_43 AC 4 ms
6,944 KB
testcase_44 AC 4 ms
6,940 KB
testcase_45 AC 264 ms
29,616 KB
testcase_46 AC 279 ms
27,136 KB
testcase_47 AC 263 ms
28,800 KB
testcase_48 AC 221 ms
27,780 KB
testcase_49 AC 219 ms
27,392 KB
testcase_50 AC 216 ms
28,544 KB
testcase_51 AC 288 ms
28,800 KB
testcase_52 AC 259 ms
27,392 KB
testcase_53 AC 264 ms
28,044 KB
testcase_54 AC 282 ms
28,928 KB
testcase_55 AC 298 ms
28,928 KB
testcase_56 AC 280 ms
28,416 KB
testcase_57 AC 258 ms
27,008 KB
testcase_58 AC 256 ms
28,180 KB
testcase_59 AC 247 ms
29,492 KB
testcase_60 AC 234 ms
29,228 KB
testcase_61 AC 242 ms
29,056 KB
testcase_62 AC 243 ms
27,264 KB
testcase_63 AC 298 ms
29,440 KB
testcase_64 AC 271 ms
29,184 KB
testcase_65 AC 514 ms
27,524 KB
testcase_66 AC 536 ms
28,544 KB
testcase_67 AC 310 ms
27,136 KB
testcase_68 AC 295 ms
27,916 KB
testcase_69 AC 511 ms
28,416 KB
testcase_70 AC 385 ms
29,348 KB
testcase_71 AC 395 ms
28,928 KB
testcase_72 AC 345 ms
27,136 KB
testcase_73 AC 258 ms
27,648 KB
testcase_74 AC 380 ms
28,416 KB
testcase_75 AC 469 ms
27,008 KB
testcase_76 AC 344 ms
27,916 KB
testcase_77 AC 527 ms
27,008 KB
testcase_78 AC 572 ms
29,224 KB
testcase_79 AC 557 ms
29,348 KB
testcase_80 AC 390 ms
28,176 KB
testcase_81 AC 468 ms
27,520 KB
testcase_82 AC 490 ms
28,544 KB
testcase_83 AC 387 ms
29,616 KB
testcase_84 AC 367 ms
28,672 KB
testcase_85 AC 577 ms
29,220 KB
testcase_86 AC 514 ms
27,008 KB
testcase_87 AC 53 ms
28,176 KB
testcase_88 AC 51 ms
27,008 KB
testcase_89 AC 2 ms
6,940 KB
testcase_90 AC 2 ms
6,944 KB
testcase_91 AC 2 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define overload(_1, _2, _3, name, ...) name
#define _for(i, a, b) for(int i = int(a); i<int(b); ++i)
#define _rep(i, n) _for(i, 0, n)
#define rep(...) overload(__VA_ARGS__, _for, _rep,)(__VA_ARGS__)
#define _rfor(i, a, b) for(int i = int(a) - 1; i >= int(b); --i)
#define _rrep(i, n) _rfor(i, n, 0)
#define rrep(...) overload(__VA_ARGS__, _rfor, _rrep,)(__VA_ARGS__)
template<class T> inline bool chmax(T&a, T b){ if(a < b){a = b; return 1;} return 0; }
template<class T> inline bool chmin(T&a, T b){ if(a > b){a = b; return 1;} return 0; }

struct Bit_Vector {
    int n, m;
    vector<uint64_t> bit;
    vector<int> sum;

    Bit_Vector(int n) : n(n), m((n + 63) / 64), bit(m), sum(m + 1) {}

    void set(int k) { bit[k / 64] |= 1ULL << (k % 64); }

    void build() { rep(i, m) sum[i + 1] = sum[i] + __builtin_popcountll(bit[i]); }
    
    bool operator[](int k) const { return (bit[k / 64] >> (k % 64)) & 1ULL; }
   
    int rank(int r, bool b) const {
        int one = sum[r / 64];
        if(r & 63) one += __builtin_popcountll(bit[r / 64] & ((1ULL << (r % 64)) - 1));
        return b ? one : r - one;
    }
    
    int rank(int l, int r, bool b) const { return rank(r, b) - rank(l, b); }
};

template<typename T>
struct Wavelet_Matrix {
    int maxlog, n;
    vector<Bit_Vector> matrix;
    vector<int> zero_cnt;
    vector<vector<ll>> cs;

    Wavelet_Matrix(vector<T> data, ll max_v) : n(data.size()) {
        T min_v = n ? *min_element(data.begin(), data.end()) : 0;
        assert(0 <= min_v);
        maxlog = max(64 - __builtin_clzll(max_v), 1);
        matrix.resize(maxlog, Bit_Vector(n));
        cs.resize(maxlog, vector<ll>(n + 1));
        zero_cnt.resize(maxlog);
        vector<T> zero(n), one(n);

        rep(i, maxlog) {
            int z = 0, o = 0;
            rep(j, n) {
                if ((data[j] >> (maxlog - 1 - i)) & 1) {
                    one[o++] = data[j];
                    matrix[i].set(j);
                } 
                else {
                    zero[z++] = data[j];
                    zero_cnt[i]++;
                }
            }
            matrix[i].build();
            data.swap(zero);
            rep(i, o) data[z + i] = one[i];
            rep(j, n) cs[i][j + 1] = cs[i][j] + data[j];
        }
    }

    T access(int k) {
        T ret = 0;
        rep(i, maxlog) {
            bool bit = matrix[i][k];
            ret = (ret << 1) | bit;
            k = matrix[i].rank(k, bit) + zero_cnt[i] * bit;
        }
        return ret;
    }

    int rank(int l, int r, T x) {
        rep(i, maxlog) {
            bool bit = (x >> (maxlog - 1 - i)) & 1;
            l = matrix[i].rank(l, bit) + zero_cnt[i] * bit;
            r = matrix[i].rank(r, bit) + zero_cnt[i] * bit;
        }
        return r - l;
    }
   
    T kth_smallest(int l, int r, int k) const {
        assert(0 <= k && k < r - l);
        T res = 0;
        rep(i, maxlog) {
            int zero = matrix[i].rank(l, r, 0);
            bool bit = k >= zero;
            l = matrix[i].rank(l, bit) + zero_cnt[i] * bit;
            r = matrix[i].rank(r, bit) + zero_cnt[i] * bit;
            res |= (T(1) << (maxlog - 1 - i)) * bit;
            k -= zero * bit;
        }
        return res;
    }

    T kth_largest(int l, int r, int k) { kth_smallest(l, r, r - l - k - 1); }

    tuple<int, int, int> rank_all(int l, int r, T x) const {
        int lt_cnt = 0, eq_cnt = r - l , mt_cnt = 0;
        rep(i, maxlog) {
            int tmp = r - l;
            bool bit = (x >> (maxlog - 1 - i)) & 1;
            l = matrix[i].rank(l, bit) + zero_cnt[i] * bit;
            r = matrix[i].rank(r, bit) + zero_cnt[i] * bit;
            int d = tmp - (r - l);
            eq_cnt -= d;
            (bit ? lt_cnt : mt_cnt) += d;
        }
        return { lt_cnt, eq_cnt, mt_cnt };
    }

    int range_freq(int l, int r, T lower, T upper) {
        auto l_cnt = get<0>(rank_all(l, r, lower));
        auto r_cnt = get<0>(rank_all(l, r, upper));
        return r_cnt - l_cnt;        
    }

    T prev_value(int l, int r, T upper) {
        int cnt = get<0>(rank_all(l, r, upper));
        return cnt == 0 ? T(-1) : kth_smallest(l, r, --cnt);
    } 

    T next_value(int l, int r, T lower) {
        int cnt = get<0>(rank_all(l, r, lower));
        return cnt == r - l ? T(-1) : kth_smallest(l, r, cnt);
    }

    ll sum_less_than(int l, int r, T x) {
        ll ret = 0;
        rep(i, maxlog){
            bool bit = (x >> (maxlog - 1 - i) & 1);
            if(bit) ret += cs[i][matrix[i].rank(r, 0)] - cs[i][matrix[i].rank(l, 0)];
            l = matrix[i].rank(l, bit) + zero_cnt[i] * bit;
            r = matrix[i].rank(r, bit) + zero_cnt[i] * bit;
        }
        return ret;
    }

    ll range_sum(int l, int r, T lower, T upper) { 
        return sum_less_than(l, r, upper) - sum_less_than(l, r, lower);
    }
};

int main () {
    cin.tie(0) -> sync_with_stdio(false);

    int n, k;
    cin >> n >> k;

    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    Wavelet_Matrix<int> wm(a, 2e9);

    ll ans = 9e18;
    for(int i = 0; i + k <= n; i++) {
        ll m = wm.kth_smallest(i, i + k, k / 2);
        ll lc = wm.range_freq(i, i + k, 0, m);
        ll ls = wm.range_sum(i, i + k, 0, m);
        ll mc = wm.range_freq(i, i + k, m + 1, 1e9 + 1);
        ll ms = wm.range_sum(i, i + k, m + 1, 1e9 + 1);
        chmin(ans, (m * lc - ls) + (ms - m * mc));
    }

    cout << ans << '\n';

    return 0;
}
0