結果

問題 No.738 平らな農地
ユーザー sonotarousonotarou
提出日時 2022-09-20 20:28:05
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 579 ms / 2,000 ms
コード長 5,521 bytes
コンパイル時間 2,757 ms
コンパイル使用メモリ 226,084 KB
実行使用メモリ 29,468 KB
最終ジャッジ日時 2023-08-23 19:39:07
合計ジャッジ時間 26,209 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 12 ms
4,380 KB
testcase_06 AC 15 ms
4,376 KB
testcase_07 AC 9 ms
4,380 KB
testcase_08 AC 6 ms
4,380 KB
testcase_09 AC 4 ms
4,380 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 6 ms
4,380 KB
testcase_12 AC 3 ms
4,376 KB
testcase_13 AC 11 ms
4,376 KB
testcase_14 AC 5 ms
4,380 KB
testcase_15 AC 291 ms
26,996 KB
testcase_16 AC 294 ms
27,804 KB
testcase_17 AC 376 ms
27,416 KB
testcase_18 AC 357 ms
26,884 KB
testcase_19 AC 451 ms
28,928 KB
testcase_20 AC 300 ms
27,656 KB
testcase_21 AC 404 ms
28,844 KB
testcase_22 AC 315 ms
27,676 KB
testcase_23 AC 407 ms
28,140 KB
testcase_24 AC 420 ms
27,876 KB
testcase_25 AC 4 ms
4,376 KB
testcase_26 AC 4 ms
4,376 KB
testcase_27 AC 4 ms
4,380 KB
testcase_28 AC 4 ms
4,380 KB
testcase_29 AC 4 ms
4,376 KB
testcase_30 AC 4 ms
4,380 KB
testcase_31 AC 4 ms
4,376 KB
testcase_32 AC 4 ms
4,376 KB
testcase_33 AC 4 ms
4,380 KB
testcase_34 AC 4 ms
4,376 KB
testcase_35 AC 4 ms
4,380 KB
testcase_36 AC 4 ms
4,380 KB
testcase_37 AC 4 ms
4,376 KB
testcase_38 AC 5 ms
4,376 KB
testcase_39 AC 4 ms
4,376 KB
testcase_40 AC 4 ms
4,376 KB
testcase_41 AC 5 ms
4,380 KB
testcase_42 AC 4 ms
4,380 KB
testcase_43 AC 4 ms
4,380 KB
testcase_44 AC 4 ms
4,376 KB
testcase_45 AC 264 ms
29,468 KB
testcase_46 AC 276 ms
27,020 KB
testcase_47 AC 262 ms
28,720 KB
testcase_48 AC 221 ms
27,520 KB
testcase_49 AC 218 ms
27,388 KB
testcase_50 AC 215 ms
28,460 KB
testcase_51 AC 288 ms
28,660 KB
testcase_52 AC 256 ms
27,412 KB
testcase_53 AC 262 ms
27,892 KB
testcase_54 AC 278 ms
28,932 KB
testcase_55 AC 296 ms
28,576 KB
testcase_56 AC 279 ms
28,440 KB
testcase_57 AC 255 ms
27,096 KB
testcase_58 AC 254 ms
28,156 KB
testcase_59 AC 245 ms
29,456 KB
testcase_60 AC 232 ms
29,192 KB
testcase_61 AC 241 ms
28,844 KB
testcase_62 AC 242 ms
27,168 KB
testcase_63 AC 297 ms
29,444 KB
testcase_64 AC 269 ms
28,920 KB
testcase_65 AC 512 ms
27,568 KB
testcase_66 AC 534 ms
28,460 KB
testcase_67 AC 305 ms
27,092 KB
testcase_68 AC 291 ms
27,944 KB
testcase_69 AC 499 ms
28,472 KB
testcase_70 AC 372 ms
29,104 KB
testcase_71 AC 394 ms
28,928 KB
testcase_72 AC 340 ms
27,116 KB
testcase_73 AC 256 ms
27,684 KB
testcase_74 AC 376 ms
28,340 KB
testcase_75 AC 465 ms
27,024 KB
testcase_76 AC 341 ms
27,948 KB
testcase_77 AC 518 ms
27,152 KB
testcase_78 AC 566 ms
29,192 KB
testcase_79 AC 552 ms
29,204 KB
testcase_80 AC 395 ms
28,192 KB
testcase_81 AC 469 ms
27,400 KB
testcase_82 AC 498 ms
28,468 KB
testcase_83 AC 384 ms
29,404 KB
testcase_84 AC 366 ms
28,716 KB
testcase_85 AC 579 ms
29,104 KB
testcase_86 AC 507 ms
27,036 KB
testcase_87 AC 53 ms
28,156 KB
testcase_88 AC 50 ms
27,100 KB
testcase_89 AC 2 ms
4,380 KB
testcase_90 AC 2 ms
4,376 KB
testcase_91 AC 2 ms
4,380 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