結果
問題 | No.738 平らな農地 |
ユーザー | kazuma |
提出日時 | 2018-09-28 22:28:41 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 985 ms / 2,000 ms |
コード長 | 5,158 bytes |
コンパイル時間 | 2,468 ms |
コンパイル使用メモリ | 217,760 KB |
実行使用メモリ | 80,232 KB |
最終ジャッジ日時 | 2024-04-20 11:12:28 |
合計ジャッジ時間 | 35,445 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,944 KB |
testcase_05 | AC | 15 ms
6,940 KB |
testcase_06 | AC | 17 ms
6,944 KB |
testcase_07 | AC | 13 ms
6,944 KB |
testcase_08 | AC | 7 ms
6,940 KB |
testcase_09 | AC | 4 ms
6,944 KB |
testcase_10 | AC | 3 ms
6,940 KB |
testcase_11 | AC | 7 ms
6,944 KB |
testcase_12 | AC | 4 ms
6,944 KB |
testcase_13 | AC | 13 ms
6,944 KB |
testcase_14 | AC | 6 ms
6,940 KB |
testcase_15 | AC | 483 ms
75,112 KB |
testcase_16 | AC | 495 ms
76,152 KB |
testcase_17 | AC | 596 ms
75,720 KB |
testcase_18 | AC | 572 ms
74,588 KB |
testcase_19 | AC | 690 ms
78,936 KB |
testcase_20 | AC | 506 ms
76,172 KB |
testcase_21 | AC | 665 ms
79,012 KB |
testcase_22 | AC | 530 ms
76,404 KB |
testcase_23 | AC | 642 ms
77,308 KB |
testcase_24 | AC | 652 ms
76,524 KB |
testcase_25 | AC | 5 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,944 KB |
testcase_31 | AC | 4 ms
6,940 KB |
testcase_32 | AC | 4 ms
6,944 KB |
testcase_33 | AC | 6 ms
6,940 KB |
testcase_34 | AC | 5 ms
6,940 KB |
testcase_35 | AC | 4 ms
6,944 KB |
testcase_36 | AC | 5 ms
6,944 KB |
testcase_37 | AC | 5 ms
6,940 KB |
testcase_38 | AC | 5 ms
6,940 KB |
testcase_39 | AC | 4 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,940 KB |
testcase_43 | AC | 4 ms
6,944 KB |
testcase_44 | AC | 4 ms
6,944 KB |
testcase_45 | AC | 443 ms
79,952 KB |
testcase_46 | AC | 455 ms
75,176 KB |
testcase_47 | AC | 457 ms
78,276 KB |
testcase_48 | AC | 394 ms
76,308 KB |
testcase_49 | AC | 391 ms
75,748 KB |
testcase_50 | AC | 383 ms
77,920 KB |
testcase_51 | AC | 491 ms
78,748 KB |
testcase_52 | AC | 434 ms
75,740 KB |
testcase_53 | AC | 449 ms
76,912 KB |
testcase_54 | AC | 482 ms
78,692 KB |
testcase_55 | AC | 499 ms
78,452 KB |
testcase_56 | AC | 471 ms
77,800 KB |
testcase_57 | AC | 439 ms
75,096 KB |
testcase_58 | AC | 438 ms
77,448 KB |
testcase_59 | AC | 431 ms
80,044 KB |
testcase_60 | AC | 404 ms
79,420 KB |
testcase_61 | AC | 429 ms
78,932 KB |
testcase_62 | AC | 417 ms
75,204 KB |
testcase_63 | AC | 506 ms
79,924 KB |
testcase_64 | AC | 459 ms
78,956 KB |
testcase_65 | AC | 756 ms
76,092 KB |
testcase_66 | AC | 792 ms
77,764 KB |
testcase_67 | AC | 536 ms
74,796 KB |
testcase_68 | AC | 535 ms
76,400 KB |
testcase_69 | AC | 865 ms
77,620 KB |
testcase_70 | AC | 668 ms
79,316 KB |
testcase_71 | AC | 134 ms
55,700 KB |
testcase_72 | AC | 602 ms
74,708 KB |
testcase_73 | AC | 392 ms
73,788 KB |
testcase_74 | AC | 744 ms
77,260 KB |
testcase_75 | AC | 782 ms
74,880 KB |
testcase_76 | AC | 599 ms
76,724 KB |
testcase_77 | AC | 863 ms
74,568 KB |
testcase_78 | AC | 946 ms
78,984 KB |
testcase_79 | AC | 985 ms
79,368 KB |
testcase_80 | AC | 683 ms
77,420 KB |
testcase_81 | AC | 802 ms
75,296 KB |
testcase_82 | AC | 797 ms
77,648 KB |
testcase_83 | AC | 687 ms
80,232 KB |
testcase_84 | AC | 603 ms
78,476 KB |
testcase_85 | AC | 907 ms
79,432 KB |
testcase_86 | AC | 841 ms
74,660 KB |
testcase_87 | AC | 157 ms
77,160 KB |
testcase_88 | AC | 147 ms
74,936 KB |
testcase_89 | AC | 2 ms
6,944 KB |
testcase_90 | AC | 2 ms
6,944 KB |
testcase_91 | AC | 1 ms
6,940 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; class fid { int n; vector<bool> data; vector<int> ra, se0, se1; public: fid(int n_) : n(n_), data(n), ra(n + 1) {} void set(int i) { data[i] = true; } void build() { for (int i = 0; i < n; i++) { ra[i + 1] = ra[i] + data[i]; } for (int i = 0; i < n; i++) { (data[i] ? se1 : se0).push_back(i); } } int rank(int i, bool b) const { return b ? ra[i] : i - ra[i]; } int rank(int l, int r, bool b) const { return rank(r, b) - rank(l, b); } int select(int x, bool b) const { return (b ? se1 : se0)[x]; } int select(int l, int x, bool b) const { return select(x + rank(l, b), b); } }; template <typename T> class wavelet_matrix { T h; int n; vector<fid> data; vector<int> mid; T get_h(T val) { T res = 1; while ((1LL << res) <= val) ++res; return res; } public: wavelet_matrix(const vector<T>& data_) : h(get_h(*max_element(data_.begin(), data_.end()))), n(data_.size()), mid(h) { data.assign(h, n); vector<T> ar1(data_), ar2(n); for (T b = 0; b < h; b++) { int p = 0; for (int i = 0; i < n; i++) { if ((ar1[i] & ((T)1 << (h - 1 - b))) == 0) { ar2[p++] = ar1[i]; } } mid[b] = p; for (int i = 0; i < n; i++) { if (ar1[i] & ((T)1 << (h - 1 - b))) { data[b].set(i); ar2[p++] = ar1[i]; } } data[b].build(); ar1.swap(ar2); } } int rank(int p, T val) { return rank(0, p, val); } int rank(int l, int r, T val) { if (val >> h) return 0; for (T b = 0; b < h; b++) { if (val & ((T)1 << (h - 1 - b))) { l = data[b].rank(l, true) + mid[b]; r = data[b].rank(r, true) + mid[b]; } else { l = data[b].rank(l, false); r = data[b].rank(r, false); } } return r - l; } int rank_less_than(int l, int r, T ub) { if (ub >> h) return r - l; int res = 0; for (T b = 0; b < h; b++) { bool d = (ub >> (h - 1 - b)) & 1; int lcnt = data[b].rank(l, d); int rcnt = data[b].rank(r, d); if (d) res += (r - l) - (rcnt - lcnt); l = lcnt; r = rcnt; if (d) { l += mid[b]; r += mid[b]; } } return res; } int rank_range(int l, int r, T lb, T ub) { return rank_less_than(l, r, ub) - rank_less_than(l, r, lb); } int select(int x, T val) { static int left[h]; int l = 0, r = n; for (T b = 0; b < h; b++) { left[b] = l; if (val & ((T)1 << (h - 1 - b))) { l = data[b].rank(l, true) + mid[b]; r = data[b].rank(r, true) + mid[b]; } else { l = data[b].rank(l, false); r = data[b].rank(r, false); } } for (int b = h - 1; b >= 0; b--) { x = data[b].select(left[b], x, (bool)((val >> (h - 1 - b)) & 1)) - left[b]; } return x; } int select(int l, int r, int x, T val) { return select(x + rank(l, val), val); } T kth_element(int l, int r, int k) { T res = 0; for (T b = 0; b < h; b++) { int cnt = data[b].rank(l, r, false); res <<= 1; if (k >= cnt) { l = data[b].rank(l, true) + mid[b]; r = data[b].rank(r, true) + mid[b]; k -= cnt; res |= 1; } else { l = data[b].rank(l, false); r = data[b].rank(r, false); } } return res; } }; template <typename T> class merge_tree { const int n; vector<vector<T>> data, sum; int size(int x) { int res = 1; while (res < x) res <<= 1; return res; } T query1(int node, T val) { int ub = lower_bound(data[node].begin(), data[node].end(), val) - data[node].begin(); return sum[node][ub] - sum[node][0]; } T query2(int node, T val) { int ub = lower_bound(data[node].begin(), data[node].end(), val) - data[node].begin(); return sum[node].back() - sum[node][ub]; } public: merge_tree(const vector<T>& data_) : n(size(data_.size())), data(n * 2), sum(n * 2) { for (int i = 0; i < (int)data_.size(); i++) data[i + n].push_back(data_[i]); for (int i = n - 1; i >= 0; i--) merge(data[i * 2].begin(), data[i * 2].end(), data[i * 2 + 1].begin(), data[i * 2 + 1].end(), back_inserter(data[i])); for (int i = 0; i < n * 2; i++) { sum[i].assign(data[i].size() + 1, 0); for (int j = 0; j < (int)data[i].size(); j++) { sum[i][j + 1] = sum[i][j] + data[i][j]; } } } T find1(int l, int r, T val) { l += n; r += n; T res = 0; while (l < r) { if (l & 1) res += query1(l++, val); if (r & 1) res += query1(--r, val); l >>= 1; r >>= 1; } return res; } T find2(int l, int r, T val) { l += n; r += n; T res = 0; while (l < r) { if (l & 1) res += query2(l++, val); if (r & 1) res += query2(--r, val); l >>= 1; r >>= 1; } return res; } }; int main() { int N, K; cin >> N >> K; vector<ll> A(N); for (int i = 0; i < N; i++) { cin >> A[i]; } wavelet_matrix<ll> wm(A); merge_tree<ll> mt(A); ll res = LLONG_MAX; for (int i = 0; i + K <= N; i++) { ll lb = 1, ub = 1e9 + 1; while (ub - lb > 1) { ll c = (lb + ub) >> 1; if (wm.rank_less_than(i, i + K, c) < (K + 1) / 2) { lb = c; } else { ub = c; } } res = min(res, (wm.rank_less_than(i, i + K, lb) * lb - mt.find1(i, i + K, lb)) + (mt.find2(i, i + K, lb) - (ll)(K - wm.rank_less_than(i, i + K, lb)) * lb)); } cout << res << endl; return 0; }