結果
問題 | No.738 平らな農地 |
ユーザー |
![]() |
提出日時 | 2018-09-28 22:39:56 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,051 ms / 2,000 ms |
コード長 | 8,012 bytes |
コンパイル時間 | 2,220 ms |
コンパイル使用メモリ | 215,748 KB |
最終ジャッジ日時 | 2025-01-06 13:57:31 |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 87 |
ソースコード
#include <bits/stdc++.h>#include <cstdio>#include <string>using namespace std;#define INF 100000000#define YJ 1145141919#define INF_INT_MAX 2147483647#define INF_LL_MAX 9223372036854775807#define EPS 1e-10#define MOD 1000000007#define Pi acos(-1)#define LL long long#define ULL unsigned long long#define LD long doubleclass Node {public:Node(unsigned long long int lIndex = startLeftIndex, unsigned long long int rIndex = endRightIndex, LL v = unitValue) : leftIndex(lIndex),rightIndex(rIndex), value(v) {}Node operator + (const Node& monoid) const {return Node(startLeftIndex, endRightIndex, this->getValue() + monoid.getValue());}static Node unit() {return Node(unitValue);}void setValue(LL l) {this->value = l;}LL getValue() const {return this->value;}pair<LL, LL> getIndexRange() {return make_pair(leftIndex, rightIndex);}bool isLeafNode() {auto it = getIndexRange();return it.second - it.first <= 1;}//値の設定void setValue(unsigned long long int index, LL value) {auto indexRange = getIndexRange();unsigned long long int leftIndex = indexRange.first, midIndex = (indexRange.first + indexRange.second)/2, rightIndex = indexRange.second;if(isLeafNode()) {if(leftIndex <= index && index < rightIndex) {setValue(value);}return;}if(!left_child) {left_child = unique_ptr<Node>(new Node(leftIndex, midIndex));}if(!right_child) {right_child = unique_ptr<Node>(new Node(midIndex, rightIndex));}if(leftIndex <= index && index < midIndex) {left_child->setValue(index, value);} else {right_child->setValue(index, value);}//戻るときに値を更新していくNode lNode, rNode; lNode.setValue(left_child->getValue()); rNode.setValue(right_child->getValue());setValue((lNode + rNode).getValue());}LL query(unsigned long long int l, unsigned long long int r) {auto indexRange = getIndexRange();if(l <= indexRange.first && indexRange.second <= r) {return getValue();} else if(indexRange.second <= l || r <= indexRange.first) {return Node::unit().getValue();} else {LL ll = Node::unit().getValue(), rr = Node::unit().getValue();if(left_child) {ll = left_child->query(l, r);}if(right_child) {rr = right_child->query(l, r);}Node lNode, rNode;lNode.setValue(ll); rNode.setValue(rr);return (lNode + rNode).getValue();}}private:LL value;static const LL unitValue = 0;static const LL startLeftIndex = 0, endRightIndex = 1145141919810;unique_ptr<Node> left_child, right_child;unsigned long long int leftIndex, rightIndex;};template <class T>class SegmentTree {public:SegmentTree() {root = unique_ptr<Node>(new Node());}void setValue(unsigned long long int index, LL value) {root->setValue(index, value);}LL query(unsigned long long int l, unsigned long long int r) {return root->query(l, r);}private:unique_ptr<T> root;};#define int long longtypedef pair<LL, int> Key;typedef int Value;struct Treap{Key key; //キーValue value; //値Treap *ch[2]; //左、右int pri; //優先度 大きい方が上に来るようにするint cnt; //部分木のサイズint sum; //部分木の値の和Treap(const Key &key, const Value &value) : key(key), value(value), pri(rand()), cnt(1), sum(value) {ch[0] = ch[1] = NULL;}};//部分木のサイズを取得int countTreap(Treap *t){return !t ? 0 : t->cnt;}//部分木の和を取得int sumTreap(Treap *t){return !t ? 0 : t->sum;}//部分木のサイズや和は部分木に何かしらの操作を加えるた度に更新を行って//整合性を保つTreap *updateTreap(Treap *t){t->cnt = countTreap(t->ch[0]) + countTreap(t->ch[1]) + 1;t->sum = sumTreap(t->ch[0]) + sumTreap(t->ch[1]) + t->value;return t;}//b:0 左回転 1 右回転Treap *rotateTreap(Treap *t, int b){Treap *s = t->ch[1-b];t->ch[1-b] = s->ch[b];s->ch[b] = t;updateTreap(t); updateTreap(s);return s;}//tが根となっている木に(key, value)を挿入Treap *insertTreap(Treap *t, const Key &key, const Value &value){if(!t) return new Treap(key, value);else if(key == t->key) return t;int b = !(key < t->key);t->ch[b] = insertTreap(t->ch[b], key, value);updateTreap(t);//優先度が大きい方が上に来るようにするif(t->pri < t->ch[b]->pri)t = rotateTreap(t, 1-b);return t;}//key値のものを取り出すTreap *findTreap(Treap *t, const Key &key){return !t || key == t->key ? t : findTreap(t->ch[t->key < key], key);}//index(0-index)番目の要素を参照するTreap *findIndexTreap(Treap *t, int index = 0){//現在指しているポインタがNULLか、indexが現在の部分木のサイズ外を指している場合if(!t || t->cnt <= index) return NULL;if(t->ch[0]){if(index < t->ch[0]->cnt){return findIndexTreap(t->ch[0], index);}else{index = index - (t->ch[0]->cnt);if(index == 0)return t;elsereturn findIndexTreap(t->ch[1], index-1);}}else if(t->ch[1]){if(index == 0)return t;elsereturn findIndexTreap(t->ch[1], index - 1);}else{if(index == 0)return t;elsereturn NULL;}}//key値のノードを削除するTreap *eraseTreap(Treap *t, const Key &key){if(!t)return NULL;if(key == t->key){if(!t->ch[0] && !t->ch[1]){//tの内容を初期化するreturn NULL;}else if(!t->ch[0])t = rotateTreap(t, 0);else if(!t->ch[1])t = rotateTreap(t, 1);elset = rotateTreap(t, !(t->ch[0]->pri < t->ch[1]->pri));t = eraseTreap(t, key);}else{int b = !(key < t->key);t->ch[b] = eraseTreap(t->ch[b], key);}updateTreap(t);return t;}const int MAX_N = 100005;const int MAX_K = 100005;int N, K;int A[MAX_N];SegmentTree<Node> segmentTree;SegmentTree<Node> segmentTreeCount;signed main(){Treap *root = NULL;cin >> N >> K;for(int i = 0; i < N; i++) {cin >> A[i];}int sum = 0;int ans = 1145141919810364;for(int i = 0; i < N; i++) {sum += A[i];root = insertTreap(root, Key(A[i], i), A[i]);segmentTree.setValue(A[i], segmentTree.query(A[i], A[i]+1) + A[i]);segmentTreeCount.setValue(A[i], segmentTreeCount.query(A[i], A[i]+1)+1);if(countTreap(root) == K) {Treap *t = findIndexTreap(root, (K-1)/2);int mid = t->value;int L = 0, R = 0;int lCount = segmentTreeCount.query(0, mid);int rCount = segmentTreeCount.query(mid+1, 1e9+7);L = mid*lCount - segmentTree.query(0, mid);R = segmentTree.query(mid+1, 1e9+7) - mid*rCount;// cerr << i << " " << L << " " << R << endl;// cerr << lCount << " " << rCount << " " << mid << endl;// cerr << segmentTree.query(0, mid) << " " << segmentTree.query(mid+1, 1e9+7) << endl;// cerr << endl;ans = min(ans, L+R);// cerr << i << " " << mid << " " << sum << endl;sum -= A[i-K+1];root = eraseTreap(root, Key(A[i-K+1], i-K+1));int AA = A[i-K+1];segmentTree.setValue(AA, segmentTree.query(AA,AA+1) - AA);segmentTreeCount.setValue(AA, segmentTreeCount.query(AA, AA+1)-1);}}cout << ans << endl;return 0;}