結果
問題 | No.738 平らな農地 |
ユーザー |
![]() |
提出日時 | 2018-09-28 22:47:18 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 158 ms / 2,000 ms |
コード長 | 4,101 bytes |
コンパイル時間 | 848 ms |
コンパイル使用メモリ | 93,336 KB |
実行使用メモリ | 10,240 KB |
最終ジャッジ日時 | 2024-10-12 07:06:04 |
合計ジャッジ時間 | 7,428 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 87 |
コンパイルメッセージ
main.cpp: In member function ‘std::pair<AVL<T>::node*, long long int> AVL<T>::rank(AVL<T>::node*, long long int) [with T = long long int]’: main.cpp:118:9: warning: control reaches end of non-void function [-Wreturn-type] 118 | } | ^
ソースコード
#include <iostream> #include <vector> #include <map> #include <set> #include <queue> #include <string> #include <iomanip> #include <algorithm> #include <cmath> #include <stdio.h> using namespace std; #define int long long int MOD = 1000000007; template<typename T> struct AVL { struct node { T key; int size, height, sum; node *child[2]; node(const T &key) :key(key), size(1), height(1),sum(key) { child[0] = child[1] = 0; } } *root; typedef node *pointer; AVL() { root = NULL; } pointer find(T key) { return find(root, key); } node *find(node *t, const T key) { if (t == NULL) return NULL; if (key == (t->key)) return t; else if (key < (t->key)) return find(t->child[0], key); else return find(t->child[1], key); } void insert(const T key) { root = insert(root, new node(key)); } node *insert(node *t, node *x) { if (t == NULL) return x; if ((x->key) <= (t->key)) t->child[0] = insert(t->child[0], x); else t->child[1] = insert(t->child[1], x); t->size += 1; return balance(t); } void erase(const T key) { T t = key; if (find(t) == NULL) return; root = erase(root, key); } node *erase(node *t, const int x) { if (t == NULL) return NULL; if (x == (t->key)) { return move_down(t->child[0], t->child[1]); } else { if (x < (t->key)) t->child[0] = erase(t->child[0], x); else t->child[1] = erase(t->child[1], x); t->size -= 1; return balance(t); } } node *move_down(node *t, node *rhs) { if (t == NULL) return rhs; t->child[1] = move_down(t->child[1], rhs); return balance(t); } int sz(node *t) { if (t != NULL) return t->size; return 0; } int ht(node *t) { if (t != NULL) return t->height; return 0; } int sm(node *t) { if (t != NULL) return t->sum; return 0; } node *rotate(node *t, int l, int r) { node *s = t->child[r]; t->child[r] = s->child[l]; s->child[l] = balance(t); if (t != NULL) t->size = sz(t->child[0]) + sz(t->child[1]) + 1; if (s != NULL) s->size = sz(s->child[0]) + sz(s->child[1]) + 1; if (t != NULL) t->sum = sm(t->child[0]) + sm(t->child[1]) + t->key; if (s != NULL) s->sum = sm(s->child[0]) + sm(s->child[1]) + s->key; return balance(s); } node *balance(node *t) { for (int i = 0; i < 2; i++) { if (ht(t->child[!i]) - ht(t->child[i]) < -1) { if (ht(t->child[i]->child[!i]) - ht(t->child[i]->child[i]) > 0) t->child[i] = rotate(t->child[i], i, !i); return rotate(t, !i, i); } } if (t != NULL) t->height = max(ht(t->child[0]), ht(t->child[1])) + 1; if (t != NULL) t->size = sz(t->child[0]) + sz(t->child[1]) + 1; if (t != NULL) t->sum = sm(t->child[0]) + sm(t->child[1]) + t->key; return t; } pair<pointer, int> rank(int k) { return rank(root, k); } pair<pointer, int> rank(node *t, int k) { if (t == NULL) return make_pair((pointer)NULL, (int)0); int m = sz(t->child[0]); if (k < m) { pair<pointer, int> res = rank(t->child[0], k); return res; } if (k == m) return make_pair(t, t->key + sm(t->child[0])); if (k > m) { pair<pointer, int> res = rank(t->child[1], k - m - 1); res.second += t->key + sm(t->child[0]); return res; } } int index(T key) { if (find(key) == NULL) return -1; return index(root, key); } int index(node *t, T key) { if (key == (t->key)) return sz(t->child[0]); if (key < (t->key)) return index(t->child[0], key); else return sz(t) - sz(t->child[1]) + index(t->child[1], key); } }; signed main() { cin.tie(0); ios::sync_with_stdio(false); int N, K; cin >> N >> K; vector<int> A(N); int res = (int)1 << 60; for (int i = 0; i < N; i++) { cin >> A[i]; } AVL<int> avl; int sum = 0; for (int i = 0; i < K - 1; i++) { avl.insert(A[i]); sum += A[i]; } int ans; int l = ((K + 1) / 2); for (int i = K - 1; i < N; i++) { avl.insert(A[i]); sum += A[i]; auto p = avl.rank((K - 1) / 2); ans = p.first->key * l - p.second; ans += (sum - p.second) - p.first->key * (K - l); res = min(res, ans); //cerr << i << " " << p.first->key << " " << p.second << endl; avl.erase(A[i - K + 1]); sum -= A[i - K + 1]; } cout << res << endl; }