結果
問題 | No.738 平らな農地 |
ユーザー |
![]() |
提出日時 | 2018-10-29 15:41:00 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 145 ms / 2,000 ms |
コード長 | 4,669 bytes |
コンパイル時間 | 2,591 ms |
コンパイル使用メモリ | 214,900 KB |
最終ジャッジ日時 | 2025-01-06 15:02:03 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 87 |
ソースコード
#include <bits/stdc++.h>#define rep(i, n) for (int i = 0; i < (n); i++)#define repi(i, a, b) for (int i = (a); i < (b); i++)#define all(a) (a).begin(), (a).end()using namespace std;using i32 = int;using i64 = long long;using f64 = double;using f80 = long double;using vi32 = vector<i32>;using vvi32 = vector<vi32>;using vi64 = vector<i64>;using vvi64 = vector<vi64>;using vstr = vector<string>;template <typename T> inline bool amax(T &x, T y) { if (x < y) { x = y; return true; } return false; }template <typename T> inline bool amin(T &x, T y) { if (y < x) { x = y; return true; } return false; }random_device rng;template <class Val>struct Treap {struct Node {Val v;int priority;Node *lef, *rig;int size_;Val sum;Node(Val v) : v(v), priority(rng()), lef(nullptr), rig(nullptr), size_(1), sum(v) {}int size() const { return size_; }static Node* update(Node* a) {if (a == nullptr) return nullptr;a->size_ = 1 + size(a->lef) + size(a->rig);a->sum = a->v;if (a->lef != nullptr) a->sum = a->sum + a->lef->sum;if (a->rig != nullptr) a->sum = a->sum + a->rig->sum;return a;}static int size(const Node* x) { return x == nullptr ? 0 : x->size_; }static Node* merge(Node* a, Node* b) {if (a == nullptr) return b;if (b == nullptr) return a;if (a->priority > b->priority) {a->rig = merge(a->rig, b);return update(a);} else {b->lef = merge(a, b->lef);return update(b);}}static pair<Node*, Node*> split(Node* a, int k) {if (a == nullptr) return make_pair(nullptr, nullptr);if (k <= size(a->lef)) {auto s = split(a->lef, k);a->lef = s.second;s.second = update(a);return s;} else {auto s = split(a->rig, k - size(a->lef) - 1);a->rig = s.first;s.first = update(a);return s;}}};using np = Node*;static pair<np, np> split_less(np a, Val v) {if (a == nullptr) return make_pair(nullptr, nullptr);if (a->v < v) {auto s = split_less(a->rig, v);a->rig = s.first;s.first = Node::update(a);return s;} else {auto s = split_less(a->lef, v);a->lef = s.second;s.second = Node::update(a);return s;}}static np insert_b(np a, np v) {auto lr = split_less(a, v->v);return Node::merge(Node::merge(lr.first, v), lr.second);}static np erase_b(np a, Val v) {auto lr = split_less(a, v);auto mr = Node::split(lr.second, 1);return Node::merge(lr.first, mr.second);}static np get_k(np a, int k) {while (a != nullptr) {if (k < Node::size(a->lef)) {a = a->lef;} else if (k == Node::size(a->lef)) {break;} else {k = k - Node::size(a->lef) - 1;a = a->rig;}}return a;}public:np root;Treap() : root(nullptr) {}Treap(np root) : root(root) {}Treap(Treap l, Treap r) : root(Node::merge(l.root, r.root)) {}int size() const { return Node::size(root); }pair<Treap, Treap> split_k(int k) {auto lr = Node::split(root, k);return make_pair(Treap(lr.first), Treap(lr.second));}Val operator[](int k) const {assert(size() > k);return get_k(root, k)->v;}void insert_b(const Val val) {root = insert_b(root, new Node(val));}void erase_b(const Val val) {if (contains_b(val)) root = erase_b(root, val);}bool contains_b(const Val q) const {auto a = root;while (a != nullptr) {if (a->v == q) return true;else if (a->v < q) a = a->rig;else a = a->lef;}return false;}};i64 solve(const int n, const int k, const vi32 &A) {if (k == 1) return 0;int l = (k + 1) / 2;int m = k - l;Treap<i64> treap;i64 ans = 1e18;rep(i, n) {treap.insert_b(A[i]);if (i >= k) treap.erase_b(A[i - k]);if (i >= k - 1) {i64 mid = treap[l - 1];auto splited = treap.split_k(l);i64 sum_of_lower = splited.first.root->sum;i64 sum_of_higher = splited.second.root->sum;treap = Treap<i64>(splited.first, splited.second);i64 inc_cost = mid * l - sum_of_lower;i64 dec_cost = sum_of_higher - mid * m;i64 cand = inc_cost + dec_cost;amin(ans, cand);}}return ans;}int main() {ios::sync_with_stdio(false);cin.tie(0);cout << fixed << setprecision(16);int n, k;cin >> n >> k;vi32 A(n);rep(i, n) cin >> A[i];cout << solve(n, k, A) << endl;return 0;}