結果
問題 | No.738 平らな農地 |
ユーザー | たこし |
提出日時 | 2018-09-28 22:39:56 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,252 ms / 2,000 ms |
コード長 | 8,012 bytes |
コンパイル時間 | 2,796 ms |
コンパイル使用メモリ | 218,000 KB |
実行使用メモリ | 262,272 KB |
最終ジャッジ日時 | 2024-04-20 11:18:33 |
合計ジャッジ時間 | 59,174 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 24 ms
7,936 KB |
testcase_06 | AC | 29 ms
8,832 KB |
testcase_07 | AC | 26 ms
9,088 KB |
testcase_08 | AC | 13 ms
6,144 KB |
testcase_09 | AC | 7 ms
5,376 KB |
testcase_10 | AC | 4 ms
5,376 KB |
testcase_11 | AC | 13 ms
6,272 KB |
testcase_12 | AC | 8 ms
5,376 KB |
testcase_13 | AC | 23 ms
7,936 KB |
testcase_14 | AC | 9 ms
5,376 KB |
testcase_15 | AC | 949 ms
107,264 KB |
testcase_16 | AC | 962 ms
108,928 KB |
testcase_17 | AC | 1,013 ms
108,160 KB |
testcase_18 | AC | 990 ms
106,240 KB |
testcase_19 | AC | 985 ms
113,920 KB |
testcase_20 | AC | 961 ms
109,696 KB |
testcase_21 | AC | 1,072 ms
114,560 KB |
testcase_22 | AC | 982 ms
109,696 KB |
testcase_23 | AC | 1,036 ms
111,104 KB |
testcase_24 | AC | 986 ms
109,568 KB |
testcase_25 | AC | 10 ms
5,888 KB |
testcase_26 | AC | 10 ms
5,760 KB |
testcase_27 | AC | 10 ms
5,760 KB |
testcase_28 | AC | 10 ms
5,888 KB |
testcase_29 | AC | 10 ms
5,888 KB |
testcase_30 | AC | 10 ms
5,760 KB |
testcase_31 | AC | 9 ms
5,632 KB |
testcase_32 | AC | 10 ms
5,760 KB |
testcase_33 | AC | 10 ms
5,888 KB |
testcase_34 | AC | 10 ms
5,888 KB |
testcase_35 | AC | 9 ms
5,632 KB |
testcase_36 | AC | 9 ms
5,632 KB |
testcase_37 | AC | 10 ms
5,632 KB |
testcase_38 | AC | 10 ms
5,760 KB |
testcase_39 | AC | 10 ms
6,016 KB |
testcase_40 | AC | 10 ms
5,632 KB |
testcase_41 | AC | 10 ms
5,760 KB |
testcase_42 | AC | 10 ms
5,888 KB |
testcase_43 | AC | 10 ms
5,888 KB |
testcase_44 | AC | 10 ms
5,632 KB |
testcase_45 | AC | 1,062 ms
126,080 KB |
testcase_46 | AC | 994 ms
116,864 KB |
testcase_47 | AC | 1,018 ms
122,880 KB |
testcase_48 | AC | 1,010 ms
119,424 KB |
testcase_49 | AC | 1,012 ms
118,784 KB |
testcase_50 | AC | 953 ms
122,752 KB |
testcase_51 | AC | 1,045 ms
123,776 KB |
testcase_52 | AC | 979 ms
118,528 KB |
testcase_53 | AC | 1,008 ms
120,832 KB |
testcase_54 | AC | 1,044 ms
124,288 KB |
testcase_55 | AC | 1,079 ms
124,544 KB |
testcase_56 | AC | 1,046 ms
122,240 KB |
testcase_57 | AC | 962 ms
116,224 KB |
testcase_58 | AC | 1,014 ms
121,728 KB |
testcase_59 | AC | 1,021 ms
126,464 KB |
testcase_60 | AC | 1,033 ms
125,824 KB |
testcase_61 | AC | 1,008 ms
124,800 KB |
testcase_62 | AC | 955 ms
116,608 KB |
testcase_63 | AC | 1,107 ms
126,848 KB |
testcase_64 | AC | 1,043 ms
124,672 KB |
testcase_65 | AC | 814 ms
109,056 KB |
testcase_66 | AC | 851 ms
112,768 KB |
testcase_67 | AC | 945 ms
239,872 KB |
testcase_68 | AC | 943 ms
246,656 KB |
testcase_69 | AC | 1,159 ms
250,496 KB |
testcase_70 | AC | 1,038 ms
258,688 KB |
testcase_71 | AC | 428 ms
11,904 KB |
testcase_72 | AC | 366 ms
11,392 KB |
testcase_73 | AC | 325 ms
11,648 KB |
testcase_74 | AC | 405 ms
11,904 KB |
testcase_75 | AC | 1,093 ms
241,152 KB |
testcase_76 | AC | 1,018 ms
249,728 KB |
testcase_77 | AC | 1,157 ms
241,152 KB |
testcase_78 | AC | 1,252 ms
260,096 KB |
testcase_79 | AC | 1,195 ms
262,272 KB |
testcase_80 | AC | 1,030 ms
252,288 KB |
testcase_81 | AC | 1,055 ms
244,224 KB |
testcase_82 | AC | 1,114 ms
254,080 KB |
testcase_83 | AC | 415 ms
12,160 KB |
testcase_84 | AC | 393 ms
12,032 KB |
testcase_85 | AC | 1,133 ms
178,944 KB |
testcase_86 | AC | 1,065 ms
166,144 KB |
testcase_87 | AC | 939 ms
172,928 KB |
testcase_88 | AC | 886 ms
166,656 KB |
testcase_89 | AC | 2 ms
5,376 KB |
testcase_90 | AC | 2 ms
5,376 KB |
testcase_91 | AC | 2 ms
5,376 KB |
ソースコード
#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 double class 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 long typedef 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; else return findIndexTreap(t->ch[1], index-1); } } else if(t->ch[1]){ if(index == 0) return t; else return findIndexTreap(t->ch[1], index - 1); } else{ if(index == 0) return t; else return 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); else t = 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; }