結果

問題 No.738 平らな農地
ユーザー sonotarousonotarou
提出日時 2022-09-20 20:28:05
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 561 ms / 2,000 ms
コード長 5,521 bytes
コンパイル時間 2,616 ms
コンパイル使用メモリ 218,776 KB
最終ジャッジ日時 2025-02-07 13:07:17
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 87
権限があれば一括ダウンロードができます

ソースコード

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