結果

問題 No.738 平らな農地
ユーザー たこしたこし
提出日時 2018-09-28 22:39:56
言語 C++17
(gcc 12.2.0 + boost 1.81.0)
結果
AC  
実行時間 1,133 ms / 2,000 ms
コード長 8,012 bytes
コンパイル時間 2,273 ms
コンパイル使用メモリ 221,428 KB
実行使用メモリ 262,192 KB
最終ジャッジ日時 2023-08-02 11:53:32
合計ジャッジ時間 53,144 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,384 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 1 ms
4,384 KB
testcase_03 AC 1 ms
4,380 KB
testcase_04 AC 1 ms
4,376 KB
testcase_05 AC 23 ms
8,116 KB
testcase_06 AC 26 ms
8,616 KB
testcase_07 AC 24 ms
9,076 KB
testcase_08 AC 12 ms
5,828 KB
testcase_09 AC 6 ms
4,660 KB
testcase_10 AC 4 ms
4,380 KB
testcase_11 AC 12 ms
5,956 KB
testcase_12 AC 6 ms
4,860 KB
testcase_13 AC 20 ms
7,540 KB
testcase_14 AC 8 ms
5,052 KB
testcase_15 AC 877 ms
107,224 KB
testcase_16 AC 895 ms
108,928 KB
testcase_17 AC 912 ms
107,964 KB
testcase_18 AC 908 ms
106,112 KB
testcase_19 AC 872 ms
113,524 KB
testcase_20 AC 885 ms
109,524 KB
testcase_21 AC 982 ms
114,340 KB
testcase_22 AC 889 ms
109,440 KB
testcase_23 AC 954 ms
111,072 KB
testcase_24 AC 894 ms
109,408 KB
testcase_25 AC 9 ms
5,636 KB
testcase_26 AC 9 ms
5,636 KB
testcase_27 AC 9 ms
5,596 KB
testcase_28 AC 9 ms
5,460 KB
testcase_29 AC 9 ms
5,652 KB
testcase_30 AC 8 ms
5,596 KB
testcase_31 AC 8 ms
5,468 KB
testcase_32 AC 8 ms
5,456 KB
testcase_33 AC 9 ms
5,468 KB
testcase_34 AC 9 ms
5,552 KB
testcase_35 AC 9 ms
5,408 KB
testcase_36 AC 8 ms
5,432 KB
testcase_37 AC 8 ms
5,544 KB
testcase_38 AC 9 ms
5,440 KB
testcase_39 AC 9 ms
5,684 KB
testcase_40 AC 9 ms
5,480 KB
testcase_41 AC 10 ms
5,464 KB
testcase_42 AC 8 ms
5,552 KB
testcase_43 AC 8 ms
5,660 KB
testcase_44 AC 8 ms
5,620 KB
testcase_45 AC 963 ms
125,940 KB
testcase_46 AC 892 ms
116,964 KB
testcase_47 AC 941 ms
122,752 KB
testcase_48 AC 886 ms
119,044 KB
testcase_49 AC 875 ms
118,492 KB
testcase_50 AC 873 ms
122,580 KB
testcase_51 AC 962 ms
123,640 KB
testcase_52 AC 892 ms
118,376 KB
testcase_53 AC 928 ms
120,680 KB
testcase_54 AC 964 ms
124,088 KB
testcase_55 AC 970 ms
124,128 KB
testcase_56 AC 940 ms
122,156 KB
testcase_57 AC 865 ms
116,124 KB
testcase_58 AC 925 ms
121,712 KB
testcase_59 AC 968 ms
126,316 KB
testcase_60 AC 950 ms
125,720 KB
testcase_61 AC 942 ms
124,756 KB
testcase_62 AC 900 ms
116,480 KB
testcase_63 AC 1,009 ms
127,028 KB
testcase_64 AC 950 ms
124,576 KB
testcase_65 AC 949 ms
108,936 KB
testcase_66 AC 768 ms
112,400 KB
testcase_67 AC 856 ms
239,888 KB
testcase_68 AC 857 ms
246,492 KB
testcase_69 AC 1,036 ms
250,308 KB
testcase_70 AC 948 ms
258,608 KB
testcase_71 AC 358 ms
11,924 KB
testcase_72 AC 315 ms
11,284 KB
testcase_73 AC 284 ms
11,556 KB
testcase_74 AC 353 ms
11,740 KB
testcase_75 AC 1,027 ms
241,072 KB
testcase_76 AC 938 ms
249,636 KB
testcase_77 AC 1,050 ms
240,972 KB
testcase_78 AC 1,133 ms
260,060 KB
testcase_79 AC 1,076 ms
262,192 KB
testcase_80 AC 943 ms
251,996 KB
testcase_81 AC 974 ms
244,064 KB
testcase_82 AC 1,014 ms
253,724 KB
testcase_83 AC 351 ms
12,012 KB
testcase_84 AC 336 ms
11,680 KB
testcase_85 AC 1,027 ms
178,656 KB
testcase_86 AC 950 ms
166,068 KB
testcase_87 AC 808 ms
172,788 KB
testcase_88 AC 795 ms
166,496 KB
testcase_89 AC 2 ms
4,380 KB
testcase_90 AC 1 ms
4,376 KB
testcase_91 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
}
0