結果
| 問題 | No.738 平らな農地 |
| ユーザー |
 sonotarou
|
| 提出日時 | 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 |
ソースコード
#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;}