#288159 (C++17) No.738 平らな農地

提出ソース

結果

問題	No.738 平らな農地
ユーザー	たこし
提出日時	2018-09-28 23:40:06
言語	C++17 (gcc 12.2.0 + boost 1.81.0)
結果	AC
実行時間	1,995 ms / 2,000 ms
コード長	4,939 bytes
コンパイル時間	2,362 ms
コンパイル使用メモリ	219,024 KB
実行使用メモリ	254,292 KB
最終ジャッジ日時	2023-08-02 12:13:04
合計ジャッジ時間	66,677 ms
ジャッジサーバーID （参考情報）	judge11 / judge14

このコードへのチャレンジ（β）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,376 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	2 ms 4,380 KB
testcase_03	AC	2 ms 4,380 KB
testcase_04	AC	2 ms 4,376 KB
testcase_05	AC	34 ms 7,740 KB
testcase_06	AC	39 ms 8,408 KB
testcase_07	AC	30 ms 8,616 KB
testcase_08	AC	16 ms 5,724 KB
testcase_09	AC	9 ms 4,704 KB
testcase_10	AC	4 ms 4,376 KB
testcase_11	AC	16 ms 5,912 KB
testcase_12	AC	8 ms 4,808 KB
testcase_13	AC	30 ms 7,324 KB
testcase_14	AC	12 ms 4,940 KB
testcase_15	AC	1,056 ms 100,212 KB
testcase_16	AC	1,070 ms 101,752 KB
testcase_17	AC	1,250 ms 100,828 KB
testcase_18	AC	1,213 ms 99,228 KB
testcase_19	AC	1,484 ms 106,104 KB
testcase_20	AC	1,071 ms 102,284 KB
testcase_21	AC	1,406 ms 106,824 KB
testcase_22	AC	1,155 ms 102,296 KB
testcase_23	AC	1,401 ms 103,672 KB
testcase_24	AC	1,413 ms 102,160 KB
testcase_25	AC	11 ms 5,436 KB
testcase_26	AC	11 ms 5,472 KB
testcase_27	AC	12 ms 5,372 KB
testcase_28	AC	11 ms 5,492 KB
testcase_29	AC	11 ms 5,612 KB
testcase_30	AC	11 ms 5,444 KB
testcase_31	AC	11 ms 5,320 KB
testcase_32	AC	12 ms 5,332 KB
testcase_33	AC	12 ms 5,344 KB
testcase_34	AC	10 ms 5,408 KB
testcase_35	AC	10 ms 5,292 KB
testcase_36	AC	10 ms 5,492 KB
testcase_37	AC	11 ms 5,356 KB
testcase_38	AC	11 ms 5,408 KB
testcase_39	AC	11 ms 5,644 KB
testcase_40	AC	12 ms 5,356 KB
testcase_41	AC	11 ms 5,416 KB
testcase_42	AC	10 ms 5,456 KB
testcase_43	AC	10 ms 5,440 KB
testcase_44	AC	11 ms 5,368 KB
testcase_45	AC	1,059 ms 118,232 KB
testcase_46	AC	1,074 ms 109,772 KB
testcase_47	AC	1,069 ms 115,248 KB
testcase_48	AC	934 ms 111,852 KB
testcase_49	AC	920 ms 111,536 KB
testcase_50	AC	930 ms 115,152 KB
testcase_51	AC	1,147 ms 116,108 KB
testcase_52	AC	1,003 ms 111,348 KB
testcase_53	AC	1,042 ms 113,476 KB
testcase_54	AC	1,119 ms 116,600 KB
testcase_55	AC	1,145 ms 116,820 KB
testcase_56	AC	1,074 ms 114,764 KB
testcase_57	AC	1,009 ms 108,984 KB
testcase_58	AC	1,024 ms 114,256 KB
testcase_59	AC	1,015 ms 118,680 KB
testcase_60	AC	994 ms 118,080 KB
testcase_61	AC	1,017 ms 117,052 KB
testcase_62	AC	979 ms 109,596 KB
testcase_63	AC	1,146 ms 119,068 KB
testcase_64	AC	1,060 ms 117,056 KB
testcase_65	AC	1,553 ms 101,736 KB
testcase_66	AC	1,576 ms 105,052 KB
testcase_67	AC	1,062 ms 232,556 KB
testcase_68	AC	1,045 ms 239,320 KB
testcase_69	AC	1,397 ms 243,032 KB
testcase_70	AC	1,194 ms 250,816 KB
testcase_71	AC	687 ms 4,380 KB
testcase_72	AC	543 ms 4,380 KB
testcase_73	AC	469 ms 4,376 KB
testcase_74	AC	637 ms 4,380 KB
testcase_75	AC	1,362 ms 234,312 KB
testcase_76	AC	1,157 ms 242,540 KB
testcase_77	AC	1,450 ms 234,004 KB
testcase_78	AC	1,575 ms 252,320 KB
testcase_79	AC	1,449 ms 254,292 KB
testcase_80	AC	1,170 ms 244,692 KB
testcase_81	AC	1,323 ms 237,188 KB
testcase_82	AC	1,428 ms 246,336 KB
testcase_83	AC	624 ms 4,376 KB
testcase_84	AC	565 ms 4,376 KB
testcase_85	AC	1,995 ms 171,232 KB
testcase_86	AC	1,714 ms 158,948 KB
testcase_87	AC	674 ms 165,408 KB
testcase_88	AC	642 ms 159,552 KB
testcase_89	AC	1 ms 4,376 KB
testcase_90	AC	1 ms 4,380 KB
testcase_91	AC	1 ms 4,376 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
    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];
        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 = 0, midR = 1e9+7;
            while(midR-midL > 1) {
                int mid = (midR + midL)/2;
                if(segmentTreeCount.query(0, mid+1) <= (K-1)/2) {
                    midL = mid;
                } else {
                    midR = mid;
                }
            }
            int mid = midR;
            // cerr << i << " " << mid << endl;

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

yukicoder

結果

テストケース

ソースコード