結果
問題 | No.1391 ±1 Abs Sum |
ユーザー |
![]() |
提出日時 | 2021-02-12 22:13:54 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 169 ms / 2,000 ms |
コード長 | 3,415 bytes |
コンパイル時間 | 2,363 ms |
コンパイル使用メモリ | 203,088 KB |
最終ジャッジ日時 | 2025-01-18 18:43:37 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
#include <bits/stdc++.h>using namespace std;// 0-indexedtemplate <class T>struct SegmentTree {// a,b,c: T, e:T(unit)// abc = (ab)c = a(bc)// ae = ea = atypedef function<T(T, T)> F;int n;F f;T unit;vector<T> dat;SegmentTree(){};SegmentTree(int newn, F f, T t) : f(f), unit(t) { init(newn); }SegmentTree(const vector<T> &v, F f, T t) : f(f), unit(t) {int _n = v.size();init(v.size());for (int i = 0; i < _n; ++i) dat[n + i] = v[i];for (int i = n - 1; i; --i) dat[i] = f(dat[i << 1], dat[(i << 1) | 1]);}void init(int newn) {n = 1;while (n < newn) n <<= 1;dat.assign(n << 1, unit);}// "go up" processvoid update(int k, T newdata) {dat[k += n] = newdata;while (k >>= 1) dat[k] = f(dat[k << 1], dat[(k << 1) | 1]);}// [a,b)T query(int a, int b) {T vl = unit, vr = unit;for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {if (l & 1) vl = f(vl, dat[l++]);if (r & 1) vr = f(dat[--r], vr);}return f(vl, vr);}// require: func(unit) == false// min left: st <= res && func(seg.query(st,res + 1))template <typename C>int find_left(int st, C &func, T &acc, int k, int l, int r) {if (l + 1 == r) {acc = f(acc, dat[k]);return func(acc) ? l : -1;}int mid = (l + r) >> 1;if (mid <= st) return find_left(st, func, acc, (k << 1) | 1, mid, r);if (st <= l && !func(f(acc, dat[k]))) {acc = f(acc, dat[k]);return -1;}int nres = find_left(st, func, acc, (k << 1), l, mid);if (~nres) return nres;return find_left(st, func, acc, (k << 1) | 1, mid, r);}template <typename C>int find_left(int st, C &func) {T acc = unit;return find_left(st, func, acc, 1, 0, n);}// max right: res <= st && func(seg.query(res - 1,st))template <typename C>int find_right(int st, C &func, T &acc, int k, int l, int r) {if (l + 1 == r) {acc = f(dat[k], acc);return func(acc) ? r : -1;}int mid = (l + r) >> 1;if (st <= mid) return find_right(st, func, acc, k << 1, l, mid);if (r <= st && !func(f(dat[k], acc))) {acc = f(dat[k], acc);return -1;}int nres = find_right(st, func, acc, (k << 1) | 1, mid, r);if (~nres) return nres;return find_right(st, func, acc, k << 1, l, mid);}template <typename C>int find_right(int st, C &func) {T acc = unit;return find_right(st, func, acc, 1, 0, n);}};int n, k;vector<long long> a;SegmentTree<long long> seg;long long solve();int main() {cin >> n >> k;a.resize(n);for (auto &p : a) cin >> p;cout << solve() << endl;return 0;}long long solve() {long long res = 1e17;{auto f = [](long long l, long long r) { return l + r; };seg = SegmentTree<long long>(a, f, 0);}k = n - k;for (int i = 0, id = 0; i < n; ++i) {auto calc = [&](int l, int r) {long long nres = 0;int nl = max(0, l), nr = min(r, i + 1);if (nl < nr) nres += a[i] * (nr - nl) - seg.query(nl, nr);nl = max(i + 1, l), nr = min(r, n);if (nl < nr) nres += seg.query(nl, nr) - a[i] * (nr - nl);return nres;};long long now = calc(0, n);while (id < k && abs(a[id] - a[i]) > abs(a[n - k + id] - a[i])) ++id;now -= 2 * (calc(0, id) + calc(n - k + id, n));res = min(res, now);}return res;}