結果
問題 | No.738 平らな農地 |
ユーザー | monnu |
提出日時 | 2024-02-05 06:54:05 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 305 ms / 2,000 ms |
コード長 | 9,370 bytes |
コンパイル時間 | 2,526 ms |
コンパイル使用メモリ | 191,868 KB |
実行使用メモリ | 46,688 KB |
最終ジャッジ日時 | 2024-09-28 11:31:18 |
合計ジャッジ時間 | 15,576 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
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 | 6 ms
5,376 KB |
testcase_06 | AC | 6 ms
5,376 KB |
testcase_07 | AC | 6 ms
5,376 KB |
testcase_08 | AC | 4 ms
5,376 KB |
testcase_09 | AC | 3 ms
5,376 KB |
testcase_10 | AC | 2 ms
5,376 KB |
testcase_11 | AC | 4 ms
5,376 KB |
testcase_12 | AC | 3 ms
5,376 KB |
testcase_13 | AC | 6 ms
5,376 KB |
testcase_14 | AC | 3 ms
5,376 KB |
testcase_15 | AC | 158 ms
41,312 KB |
testcase_16 | AC | 157 ms
41,712 KB |
testcase_17 | AC | 172 ms
41,196 KB |
testcase_18 | AC | 172 ms
40,908 KB |
testcase_19 | AC | 193 ms
42,696 KB |
testcase_20 | AC | 160 ms
41,588 KB |
testcase_21 | AC | 185 ms
43,080 KB |
testcase_22 | AC | 163 ms
41,468 KB |
testcase_23 | AC | 183 ms
42,012 KB |
testcase_24 | AC | 186 ms
41,856 KB |
testcase_25 | AC | 3 ms
5,376 KB |
testcase_26 | AC | 3 ms
5,376 KB |
testcase_27 | AC | 3 ms
5,376 KB |
testcase_28 | AC | 3 ms
5,376 KB |
testcase_29 | AC | 4 ms
5,376 KB |
testcase_30 | AC | 4 ms
5,376 KB |
testcase_31 | AC | 3 ms
5,376 KB |
testcase_32 | AC | 3 ms
5,376 KB |
testcase_33 | AC | 3 ms
5,376 KB |
testcase_34 | AC | 3 ms
5,376 KB |
testcase_35 | AC | 3 ms
5,376 KB |
testcase_36 | AC | 3 ms
5,376 KB |
testcase_37 | AC | 3 ms
5,376 KB |
testcase_38 | AC | 4 ms
5,376 KB |
testcase_39 | AC | 3 ms
5,376 KB |
testcase_40 | AC | 3 ms
5,376 KB |
testcase_41 | AC | 3 ms
5,376 KB |
testcase_42 | AC | 3 ms
5,376 KB |
testcase_43 | AC | 3 ms
5,376 KB |
testcase_44 | AC | 4 ms
5,376 KB |
testcase_45 | AC | 172 ms
46,052 KB |
testcase_46 | AC | 161 ms
41,176 KB |
testcase_47 | AC | 168 ms
44,852 KB |
testcase_48 | AC | 152 ms
41,592 KB |
testcase_49 | AC | 147 ms
41,328 KB |
testcase_50 | AC | 160 ms
44,720 KB |
testcase_51 | AC | 180 ms
44,984 KB |
testcase_52 | AC | 156 ms
41,200 KB |
testcase_53 | AC | 162 ms
44,300 KB |
testcase_54 | AC | 166 ms
45,136 KB |
testcase_55 | AC | 180 ms
45,372 KB |
testcase_56 | AC | 168 ms
44,452 KB |
testcase_57 | AC | 151 ms
40,788 KB |
testcase_58 | AC | 164 ms
44,448 KB |
testcase_59 | AC | 165 ms
45,952 KB |
testcase_60 | AC | 163 ms
45,396 KB |
testcase_61 | AC | 163 ms
45,264 KB |
testcase_62 | AC | 152 ms
41,184 KB |
testcase_63 | AC | 177 ms
46,688 KB |
testcase_64 | AC | 167 ms
45,516 KB |
testcase_65 | AC | 261 ms
41,328 KB |
testcase_66 | AC | 278 ms
42,280 KB |
testcase_67 | AC | 171 ms
43,484 KB |
testcase_68 | AC | 169 ms
44,176 KB |
testcase_69 | AC | 221 ms
44,576 KB |
testcase_70 | AC | 198 ms
45,404 KB |
testcase_71 | AC | 27 ms
7,492 KB |
testcase_72 | AC | 50 ms
7,264 KB |
testcase_73 | AC | 48 ms
7,292 KB |
testcase_74 | AC | 49 ms
7,460 KB |
testcase_75 | AC | 222 ms
43,220 KB |
testcase_76 | AC | 194 ms
44,172 KB |
testcase_77 | AC | 240 ms
43,476 KB |
testcase_78 | AC | 259 ms
45,744 KB |
testcase_79 | AC | 248 ms
45,916 KB |
testcase_80 | AC | 206 ms
44,700 KB |
testcase_81 | AC | 233 ms
43,884 KB |
testcase_82 | AC | 211 ms
44,716 KB |
testcase_83 | AC | 47 ms
10,348 KB |
testcase_84 | AC | 47 ms
10,160 KB |
testcase_85 | AC | 305 ms
45,264 KB |
testcase_86 | AC | 274 ms
43,348 KB |
testcase_87 | AC | 126 ms
44,832 KB |
testcase_88 | AC | 120 ms
43,220 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 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; template <class T> class WaveletMatrix { int BIT_SIZE = 0; T unit; vector<int> _a; vector<T> order; vector<vector<int>> _B; vector<vector<T>> _sum; vector<T> _finalSum; vector<vector<int>> _rank1; vector<vector<int>> _select0; vector<vector<int>> _select1; vector<int> _zeroCount; vector<int> _start, _last; int range_freq_internal(int s, int e, int low, int high, int b) { if (s > e) { return 0; } if (b == -1) { return e - s + 1; } if (low == 0 && high == ((1 << (b + 1)) - 1)) { return e - s + 1; } if (((low >> b) & 1) == 1) { int _s = _zeroCount[b] + _rank1[b][s - 1] + 1; int _e = _zeroCount[b] + _rank1[b][e]; return range_freq_internal(_s, _e, low ^ (1 << b), high ^ (1 << b), b - 1); } if (((high >> b) & 1) == 0) { int _s = (s - 1) - _rank1[b][s - 1] + 1; int _e = e - _rank1[b][e]; return range_freq_internal(_s, _e, low, high, b - 1); } int x, y; { int _s = (s - 1) - _rank1[b][s - 1] + 1; int _e = e - _rank1[b][e]; x = range_freq_internal(_s, _e, low, (1 << b) - 1, b - 1); } { int _s = _zeroCount[b] + _rank1[b][s - 1] + 1; int _e = _zeroCount[b] + _rank1[b][e]; y = range_freq_internal(_s, _e, 0, high ^ (1 << b), b - 1); } return x + y; } T range_sum_internal(int s, int e, int low, int high, int b) { if (s > e) { return unit; } if (b == -1) { if (s == 0) { return _finalSum[e]; } else { return _finalSum[e] - _finalSum[s - 1]; } } if (low == 0 && high == ((1 << (b + 1)) - 1)) { if (s == 0) { return _sum[b][e]; } else { return _sum[b][e] - _sum[b][s - 1]; } } if (((low >> b) & 1) == 1) { int _s = _zeroCount[b] + _rank1[b][s - 1] + 1; int _e = _zeroCount[b] + _rank1[b][e]; return range_sum_internal(_s, _e, low ^ (1 << b), high ^ (1 << b), b - 1); } if (((high >> b) & 1) == 0) { int _s = (s - 1) - _rank1[b][s - 1] + 1; int _e = e - _rank1[b][e]; return range_sum_internal(_s, _e, low, high, b - 1); } T x, y; { int _s = (s - 1) - _rank1[b][s - 1] + 1; int _e = e - _rank1[b][e]; x = range_sum_internal(_s, _e, low, (1 << b) - 1, b - 1); } { int _s = _zeroCount[b] + _rank1[b][s - 1] + 1; int _e = _zeroCount[b] + _rank1[b][e]; y = range_sum_internal(_s, _e, 0, high ^ (1 << b), b - 1); } return x + y; } public: WaveletMatrix(vector<T> A, T _unit) : unit(_unit) { int N = A.size(); for (int i = 0; i < N; i++) { order.push_back(A[i]); } sort(order.begin(), order.end()); order.erase(unique(order.begin(), order.end()), order.end()); while ((1 << BIT_SIZE) < order.size()) { BIT_SIZE++; } vector<int> a(N); for (int i = 0; i < N; i++) { int k = lower_bound(order.begin(), order.end(), A[i]) - order.begin(); a[i] = k; } _B.resize(BIT_SIZE); _sum.resize(BIT_SIZE); _rank1.resize(BIT_SIZE); _select0.resize(BIT_SIZE); _select1.resize(BIT_SIZE); _zeroCount.resize(BIT_SIZE, 0); for (int b = BIT_SIZE - 1; b >= 0; b--) { vector<int> a_tmp[2]; _B[b].push_back(-1); _sum[b].push_back(unit); _rank1[b].push_back(0); _select0[b].push_back(-1); _select1[b].push_back(-1); for (int i = 0; i < N; i++) { int f = (a[i] >> b) & 1; _B[b].push_back(f); _sum[b].push_back(_sum[b].back() + order[a[i]]); _rank1[b].push_back(_rank1[b].back() + f); if (f == 0) { _select0[b].push_back(i + 1); } else { _select1[b].push_back(i + 1); } a_tmp[f].push_back(a[i]); } a.clear(); for (int x : a_tmp[0]) { a.push_back(x); } for (int x : a_tmp[1]) { a.push_back(x); } _zeroCount[b] = a_tmp[0].size(); } _start = vector<int>(order.size(), -1); _last = vector<int>(order.size(), -1); for (int i = (int)a.size() - 1; i >= 0; i--) { _start[a[i]] = i + 1; } for (int i = 0; i < a.size(); i++) { _last[a[i]] = i + 1; } _finalSum.push_back(unit); for (int i = 0; i < N; i++) { _finalSum.push_back(_finalSum.back() + order[a[i]]); } _a = a; } T access(int i) { int ret = 0; for (int b = BIT_SIZE - 1; b >= 0; b--) { if (_B[b][i] == 0) { i = i - _rank1[b][i]; } else { ret += (1 << b); i = _zeroCount[b] + _rank1[b][i]; } } return order[ret]; } int rank(T x, int i) { int num = lower_bound(order.begin(), order.end(), x) - order.begin(); if (num >= order.size() || order[num] != x) { return 0; } for (int b = BIT_SIZE - 1; b >= 0; b--) { if (((num >> b) & 1) == 0) { i = i - _rank1[b][i]; if (i == 0) { return 0; } } else { if (_rank1[b][i] == 0) { return 0; } i = _zeroCount[b] + _rank1[b][i]; } } return i - _start[num] + 1; } int select(T x, int ith) { if (ith == 0) { return -1; } int num = lower_bound(order.begin(), order.end(), x) - order.begin(); if (num >= order.size() || order[num] != x) { return -1; } if (_last[num] - _start[num] + 1 < ith) { return -1; } ith = _start[num] + (ith - 1); for (int b = 0; b < BIT_SIZE; b++) { if (((num >> b) & 1) == 0) { ith = _select0[b][ith]; } else { ith = _select1[b][ith - _zeroCount[b]]; } } return ith; } T quantile(int s, int e, int r) { for (int b = BIT_SIZE - 1; b >= 0; b--) { int cnt = (e - _rank1[b][e]) - ((s - 1) - _rank1[b][s - 1]); if (cnt >= r) { s = (s - 1) - _rank1[b][s - 1] + 1; e = e - _rank1[b][e]; } else { r -= cnt; s = _zeroCount[b] + _rank1[b][s - 1] + 1; e = _zeroCount[b] + _rank1[b][e]; } } int num = _a[s - 1]; return order[num]; } int range_freq(int s, int e, T low, T high) { if (s > e) { return 0; } int l = lower_bound(order.begin(), order.end(), low) - order.begin(); int r = upper_bound(order.begin(), order.end(), high) - order.begin(); r--; if (l > r) { return 0; } return range_freq_internal(s, e, l, r, BIT_SIZE - 1); } T range_sum(int s, int e, T low, T high) { if (s > e) { return 0; } int l = lower_bound(order.begin(), order.end(), low) - order.begin(); int r = upper_bound(order.begin(), order.end(), high) - order.begin(); r--; if (l > r) { return 0; } return range_sum_internal(s, e, l, r, BIT_SIZE - 1); } }; int main() { int N, K; cin >> N >> K; vector<ll> A(N); for (int i = 0; i < N; i++) { cin >> A[i]; } WaveletMatrix<ll> wm(A, 0); ll ans = 1000000000 * (ll)N; for (int i = 1; i + K - 1 <= N; i++) { ll med = wm.quantile(i, i + K - 1, (K + 1) / 2); { ll tmp = 0; int cnt1 = wm.range_freq(i, i + K - 1, 0, med); tmp += cnt1 * med - wm.range_sum(i, i + K - 1, 0, med); int cnt2 = wm.range_freq(i, i + K - 1, med, 1000000000); tmp += wm.range_sum(i, i + K - 1, med, 1000000000) - cnt2 * med; ans = min(ans, tmp); } } cout << ans << endl; }