結果
問題 |
No.738 平らな農地
|
ユーザー |
|
提出日時 | 2018-09-28 23:25:29 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 187 ms / 2,000 ms |
コード長 | 1,951 bytes |
コンパイル時間 | 1,985 ms |
コンパイル使用メモリ | 184,192 KB |
実行使用メモリ | 12,160 KB |
最終ジャッジ日時 | 2024-10-12 07:22:04 |
合計ジャッジ時間 | 11,137 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 87 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; //引数unzipには圧縮前のvectorを入れる int compress(vector<ll>& unzip, map<ll, int>& zip) { sort(unzip.begin(), unzip.end()); unzip.erase(unique(unzip.begin(), unzip.end()), unzip.end()); for (int i = 0; i < unzip.size(); i++) { zip[unzip[i]] = i; } return unzip.size(); } //1-indexであることに注意 template <typename T> struct BIT { int n; vector<T> data; BIT(int n) : n(n), data(n + 1, 0) {} T sum(int i) { T s = 0; while (i > 0) { s += data[i]; i -= i & -i; } return s; } void add(int i, T x) { while (i <= n) { data[i] += x; i += i & -i; } } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int n, k; cin >> n >> k; vector<ll> a(n); for (int i = 0; i < n; i++) cin >> a[i]; vector<ll> unzip(a); map<ll, int> zip; compress(unzip, zip); BIT<int> b(unzip.size()); BIT<ll> b2(unzip.size()); ll ans = 1000000000000000LL; for (int i = 0; i < n; i++) { b.add(zip[a[i]] + 1, 1); b2.add(zip[a[i]] + 1, a[i]); if (i < k - 1) continue; if (i >= k) { b.add(zip[a[i - k]] + 1, -1); b2.add(zip[a[i - k]] + 1, -a[i - k]); } int ok = (int)unzip.size() - 1, ng = -1; while (ok - ng > 1) { int mid = (ok + ng) / 2; if (b.sum(mid + 1) >= (k + 1) / 2) ok = mid; else ng = mid; } ll hoge = b2.sum(unzip.size()) - b2.sum(ok + 1); ll foo = b.sum(unzip.size()) - b.sum(ok + 1); ll tmp = hoge - foo * unzip[ok]; hoge = b2.sum(ok); foo = b.sum(ok); tmp += foo * unzip[ok] - hoge; ans = min(ans, tmp); //cout << unzip[ok] << endl; } cout << ans << endl; return 0; }