結果

問題 No.738 平らな農地
ユーザー たこしたこし
提出日時 2018-09-28 23:55:40
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 1,934 ms / 2,000 ms
コード長 4,997 bytes
コンパイル時間 6,592 ms
コンパイル使用メモリ 220,924 KB
実行使用メモリ 255,056 KB
最終ジャッジ日時 2024-04-20 12:15:49
合計ジャッジ時間 13,617 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 3 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 28 ms
8,064 KB
testcase_06 AC 34 ms
8,576 KB
testcase_07 AC 27 ms
8,960 KB
testcase_08 AC 14 ms
5,888 KB
testcase_09 AC 8 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 25 ms
7,680 KB
testcase_14 AC 10 ms
5,376 KB
testcase_15 AC 965 ms
100,684 KB
testcase_16 AC 972 ms
102,604 KB
testcase_17 AC 1,125 ms
101,712 KB
testcase_18 AC 1,101 ms
99,796 KB
testcase_19 AC 1,377 ms
106,960 KB
testcase_20 AC 1,320 ms
102,860 KB
testcase_21 AC 1,416 ms
107,728 KB
testcase_22 AC 1,026 ms
103,248 KB
testcase_23 AC 1,231 ms
104,528 KB
testcase_24 AC 1,247 ms
102,736 KB
testcase_25 AC 10 ms
5,888 KB
testcase_26 AC 11 ms
5,632 KB
testcase_27 AC 11 ms
5,504 KB
testcase_28 AC 11 ms
5,760 KB
testcase_29 AC 11 ms
5,888 KB
testcase_30 AC 11 ms
5,760 KB
testcase_31 AC 10 ms
5,504 KB
testcase_32 AC 10 ms
5,632 KB
testcase_33 AC 11 ms
5,632 KB
testcase_34 AC 10 ms
5,504 KB
testcase_35 AC 10 ms
5,632 KB
testcase_36 AC 10 ms
5,760 KB
testcase_37 AC 9 ms
5,504 KB
testcase_38 AC 10 ms
5,760 KB
testcase_39 AC 11 ms
5,888 KB
testcase_40 AC 10 ms
5,760 KB
testcase_41 AC 11 ms
5,632 KB
testcase_42 AC 10 ms
5,504 KB
testcase_43 AC 10 ms
5,632 KB
testcase_44 AC 10 ms
5,760 KB
testcase_45 AC 990 ms
119,116 KB
testcase_46 AC 971 ms
110,292 KB
testcase_47 AC 969 ms
115,920 KB
testcase_48 AC 863 ms
112,588 KB
testcase_49 AC 855 ms
112,080 KB
testcase_50 AC 868 ms
115,792 KB
testcase_51 AC 1,019 ms
116,940 KB
testcase_52 AC 922 ms
112,080 KB
testcase_53 AC 965 ms
114,384 KB
testcase_54 AC 1,017 ms
117,212 KB
testcase_55 AC 1,046 ms
117,456 KB
testcase_56 AC 1,009 ms
115,648 KB
testcase_57 AC 917 ms
109,652 KB
testcase_58 AC 953 ms
114,896 KB
testcase_59 AC 954 ms
119,632 KB
testcase_60 AC 918 ms
118,940 KB
testcase_61 AC 930 ms
117,840 KB
testcase_62 AC 927 ms
110,032 KB
testcase_63 AC 1,070 ms
120,016 KB
testcase_64 AC 997 ms
117,588 KB
testcase_65 AC 1,494 ms
102,480 KB
testcase_66 AC 1,551 ms
105,940 KB
testcase_67 AC 1,013 ms
233,428 KB
testcase_68 AC 1,008 ms
239,952 KB
testcase_69 AC 1,305 ms
243,664 KB
testcase_70 AC 1,173 ms
251,476 KB
testcase_71 AC 673 ms
5,376 KB
testcase_72 AC 542 ms
5,376 KB
testcase_73 AC 461 ms
5,376 KB
testcase_74 AC 647 ms
5,376 KB
testcase_75 AC 1,262 ms
234,828 KB
testcase_76 AC 1,108 ms
243,152 KB
testcase_77 AC 1,342 ms
234,576 KB
testcase_78 AC 1,465 ms
253,140 KB
testcase_79 AC 1,292 ms
255,056 KB
testcase_80 AC 1,074 ms
245,584 KB
testcase_81 AC 1,288 ms
237,648 KB
testcase_82 AC 1,333 ms
247,000 KB
testcase_83 AC 633 ms
5,376 KB
testcase_84 AC 572 ms
5,376 KB
testcase_85 AC 1,934 ms
171,984 KB
testcase_86 AC 1,754 ms
159,568 KB
testcase_87 AC 723 ms
166,348 KB
testcase_88 AC 688 ms
160,080 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
権限があれば一括ダウンロードができます

ソースコード

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 = 1145141919;

    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

SegmentTree<Node> segmentTree;
SegmentTree<Node> segmentTreeCount;

const int MAX_N = 100005;
int N, K;
int A[MAX_N];

signed main()
{
    cin >> N >> K;
    vector<int> avec;
    for(int i = 0; i < N; i++) {
        cin >> A[i];
        avec.push_back(A[i]);
    }

    sort(begin(avec), end(avec));

    int sum = 0;
    int ans = 1145141919810364;
    for(int i = 0; i < N; i++) {
        sum += 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(i >= K-1) {
            int midL = -1, midR = avec.size();
            while(midR-midL > 1) {
                int mid = (midR + midL)/2;
                if(segmentTreeCount.query(0, avec[mid]+1) <= (K-1)/2) {
                    midL = mid;
                } else {
                    midR = mid;
                }
            }
            int mid = avec[midR];

            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;

            ans = min(ans, L+R);

            sum -= A[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