結果
問題 | No.738 平らな農地 |
ユーザー |
|
提出日時 | 2018-10-18 21:12:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 184 ms / 2,000 ms |
コード長 | 6,337 bytes |
コンパイル時間 | 2,593 ms |
コンパイル使用メモリ | 211,004 KB |
最終ジャッジ日時 | 2025-01-06 14:33:46 |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 87 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define LOCALmt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count());class node {public:int id;node* l;node* r;node* p;bool rev;int sz;// declare extra variables:int P;int64_t sum;node(int _id) {id = _id;l = r = p = NULL;rev = false;sz = 1;// init extra variables:P = rng();sum = id;}void unsafe_reverse() {rev ^= 1;swap(l, r);pull();}// apply changes:void unsafe_apply() {}void push() {if (rev) {if (l != NULL) {l->unsafe_reverse();}if (r != NULL) {r->unsafe_reverse();}rev = 0;}// now push everything else:}void pull() {sz = 1;sum = id;// now init from self:if (l != NULL) {l->p = this;sz += l->sz;// now pull from l:sum += l->sum;}if (r != NULL) {r->p = this;sz += r->sz;// now pull from r:sum += r->sum;}}};void debug_node(node* v, string pref = "") {#ifdef LOCALif (v != NULL) {debug_node(v->r, pref + " ");cerr << pref << "-"<< " " << v->id << '\n';debug_node(v->l, pref + " ");} else {cerr << pref << "-"<< " "<< "NULL" << '\n';}#endif}namespace treap {pair<node*, int> find(node* v, const function<int(node*)>& go_to) {// go_to returns: 0 -- found; -1 -- go left; 1 -- go right// find returns the last vertex on the descent and its go_toif (v == NULL) {return {NULL, 0};}int dir;while (true) {v->push();dir = go_to(v);if (dir == 0) {break;}node* u = (dir == -1 ? v->l : v->r);if (u == NULL) {break;}v = u;}return {v, dir};}node* get_leftmost(node* v) {return find(v, [&](node*) { return -1; }).first;}node* get_rightmost(node* v) {return find(v, [&](node*) { return 1; }).first;}node* get_kth(node* v, int k) { // 0-indexedpair<node*, int> p = find(v, [&](node* u) {if (u->l != NULL) {if (u->l->sz > k) {return -1;}k -= u->l->sz;}if (k == 0) {return 0;}k--;return 1;});return (p.second == 0 ? p.first : NULL);}int get_position(node* v) { // 0-indexedint k = (v->l != NULL ? v->l->sz : 0);while (v->p != NULL) {if (v == v->p->r) {k++;if (v->p->l != NULL) {k += v->p->l->sz;}}v = v->p;}return k;}node* get_bst_root(node* v) {while (v->p != NULL) {v = v->p;}return v;}pair<node*, node*> split(node* v, const function<bool(node*)>& is_right) {if (v == NULL) {return {NULL, NULL};}v->push();if (is_right(v)) {pair<node*, node*> p = split(v->l, is_right);if (p.first != NULL) {p.first->p = NULL;}v->l = p.second;v->pull();return {p.first, v};} else {pair<node*, node*> p = split(v->r, is_right);v->r = p.first;if (p.second != NULL) {p.second->p = NULL;}v->pull();return {v, p.second};}}pair<node*, node*> split_leftmost_k(node* v, int k) {return split(v, [&](node* u) {int left_and_me = (u->l != NULL ? u->l->sz : 0) + 1;if (k >= left_and_me) {k -= left_and_me;return false;}return true;});}node* merge(node* v, node* u) {if (v == NULL) {return u;}if (u == NULL) {return v;}if (v->P > u->P) {// if (rng() % (v->sz + u->sz) < (unsigned int) v->sz) {v->push();v->r = merge(v->r, u);v->pull();return v;} else {u->push();u->l = merge(v, u->l);u->pull();return u;}}int count_left(node* v, const function<bool(node*)>& is_right) {if (v == NULL) {return 0;}v->push();if (is_right(v)) {return count_left(v->l, is_right);}return (v->l != NULL ? v->l->sz : 0) + 1 + count_left(v->r, is_right);}node* add(node* r, node* v, const function<bool(node*)>& go_left) {pair<node*, node*> p = split(r, go_left);return merge(p.first, merge(v, p.second));}node* remove(node* v) { // returns the new rootv->push();node* x = v->l;node* y = v->r;node* p = v->p;v->l = v->r = v->p = NULL;v->push();v->pull(); // now v might be reusable...node* z = merge(x, y);if (p == NULL) {if (z != NULL) {z->p = NULL;}return z;}if (p->l == v) {p->l = z;}if (p->r == v) {p->r = z;}while (true) {p->push();p->pull();if (p->p == NULL) {break;}p = p->p;}return p;}node* next(node* v) {if (v->r == NULL) {while (v->p != NULL && v->p->r == v) {v = v->p;}return v->p;}v->push();v = v->r;while (v->l != NULL) {v->push();v = v->l;}return v;}node* prev(node* v) {if (v->l == NULL) {while (v->p != NULL && v->p->l == v) {v = v->p;}return v->p;}v->push();v = v->l;while (v->r != NULL) {v->push();v = v->r;}return v;}int get_size(node* v) { return (v != NULL ? v->sz : 0); }template <typename... T>void apply(node* v, T... args) {v->unsafe_apply(args...);}void reverse(node* v) { v->unsafe_reverse(); }} // namespace treapusing namespace treap;signed main() {ios::sync_with_stdio(false);int N, K;cin >> N >> K;vector<int> A(N);for (int i = 0; i < N; ++i) cin >> A[i];node* root = nullptr;for (int i = 0; i < K; ++i)root = add(root, new node(A[i]), [&](node* v) { return A[i] < v->id; });auto eval = [](node* &r) {assert(r);node* lc;node* rc;int med = get_kth(r, r->sz / 2)->id;tie(lc, rc) = split(r, [&](node* v) { return v->id > med; });int64_t ret = 0;if (lc) ret += 1LL * med * lc->sz - lc->sum;if (rc) ret += rc->sum - 1LL * med * rc->sz;r = merge(lc, rc);return ret;};int64_t ans = eval(root);for (int i = 1; i + K <= N; ++i) {root = remove(find(root, [&](node* v) {return (v->id != A[i - 1]) * (A[i - 1] < v->id ? -1 : +1); }).first);root = add(root, new node(A[i + K - 1]), [&](node* v) { return A[i + K - 1] < v->id; });ans = min(ans, eval(root));}cout << ans << endl;}