#1187084 (D) No.3303 Heal Slimes 2

• 問題: No.3303 Heal Slimes 2
• ユーザー: InTheBloom
• 提出日時: 2026-09-16 23:03:55
• 言語: D (dmd 2.113.0)
• 結果: AC
• 実行時間: 2,124 ms / 4,000 ms
• コード長: 8,872 bytes
• コンパイル時間: 4,413 ms
• コンパイル使用メモリ: 194,048 KB
• 実行使用メモリ: 14,180 KB
• 最終ジャッジ日時: 2026-09-16 23:04:43
• 合計ジャッジ時間: 46,479 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
other	AC * 32

ソースコード

import std;

void main () {
    int N, K, D;
    readln.read(N, K, D);
    auto H = readln.split.to!(int[]);

    auto seg1 = new DynamicSegmentTree!(int, (int a, int b) => a + b, () => 0)(10 ^^ 9 + 100);
    auto seg2 = new DynamicSegmentTree!(long, (long a, long b) => a + b, () => 0L)(10 ^^ 9 + 100);
    foreach (i; 0 .. K - 1) {
        seg1.set(H[i], seg1.get(H[i]) + 1);
        seg2.set(H[i], seg2.get(H[i]) + H[i]);
    }

    long ans = long.max;
    foreach (i; K - 1 .. N) {
        seg1.set(H[i], seg1.get(H[i]) + 1);
        seg2.set(H[i], seg2.get(H[i]) + H[i]);

        bool f (int x) {
            int L = seg1.prod(0, x);
            int R = seg1.prod(x + D + 1, 10 ^^ 9 + 100);

            return L - R <= 0;
        }
        auto ret = bsearch!(f)(0, 10 ^^ 9 + 10);
        // writeln(ret.value);

        foreach (d; 0 .. 2) {
            int val = ret.value + d;
            int L = seg1.prod(0, val);
            int R = seg1.prod(val + D + 1, 10 ^^ 9 + 100);

            long s = 0;
            s += (1L * L * val - seg2.prod(0, val));
            s += (seg2.prod(val + D + 1, 10 ^^ 9 + 100) - 1L * R * (val + D));

            // writefln("[%s %s), v: %s, s: %s", i - (K - 1), i + 1, val, s);
            ans = min(ans, s);
        }

        seg1.set(H[i - (K - 1)], seg1.get(H[i - (K - 1)]) - 1);
        seg2.set(H[i - (K - 1)], seg2.get(H[i - (K - 1)]) - H[i - (K - 1)]);
    }

    writeln(ans);
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

import std.traits : ReturnType, isCallable, Parameters;
import std.meta : AliasSeq;

class DynamicSegmentTree (T, alias op, alias e) {
    // TODO: assertのメッセージを表示
    static assert(isCallable!(op));
    static assert(isCallable!(e));
    static assert(is (ReturnType!(op) == T));
    static assert(is (ReturnType!(e) == T));
    static assert(is (Parameters!(op) == AliasSeq!(T, T)));
    static assert(is (Parameters!(e) == AliasSeq!()));

    // 内部が1-indexedで動的な完全二分セグメント木
    import std.format : format;
    public:
        this (long N_)
        in { assert(1 <= N_, format("Dynamic SegmentTree: N = %s does not satisfy constraints. N must be in range of [1, %s]", 4 * 10L^^18)); }
        do {
            length = N_;

            // N_以上の2冪に設定
            N = 1;
            while (N < N_) N *= 2;
        }

        void set (long idx, T val)
        in { assert(0 <= idx && idx < length, format("Dynamic SegmentTree: idx = %s does not satisfy constraints. idx must be in range of [0, %s)", idx, length)); }
        do {
            idx++;
            internal_set(root, idx, val, 1, N + 1);
        }

        T get (long idx)
        in { assert(0 <= idx && idx < length, format("Dynamic SegmentTree: idx = %s does not satisfy constraints. idx must be in range of [0, %s)", idx, length)); }
        do {
            idx++;
            return internal_get(root, idx, 1, N + 1);
        }

        T prod (long l, long r)
        in {
            assert(0 <= l && l < length, format("Dynamic SegmentTree: l = %s does not satisfy constraints. l must be in range of [0, %s)", l, length));
            assert(0 <= r && r <= length, format("Dynamic SegmentTree: r = %s does not satisfy constraints. r must be in range of [0, %s]", r, length));
            assert(l <= r, format("Dynamic SegmentTree: l = %s, r = %s does not satisfy constraints. l <= r must be satisfied.", l, r));
        }
        do {
            l++, r++;
            if (l == r) return e();
            return internal_prod(root, l, r, 1, N + 1);
        }

        T all_prod () {
            return internal_prod(root, 1, N + 1, 1, N + 1);
        }

    private:
        struct node {
            long index;
            T value, product;
            node *left = null, right = null;
        }

        void node_update (node *n) {
            n.product = op(
                    op((n.left == null ? e() : n.left.product), n.value),
                    (n.right == null ? e() : n.right.product)
                    );
        }

        node *root = null;
        long N = 0;
        long length = 0;

        // [l, r) : 今見ている部分木が管理する範囲
        node *internal_set (ref node *cur, long idx, T val, long l, long r) {
            if (cur == null) {
                return cur = new node(idx, val, val, null, null);
            }

            if (cur.index == idx) {
                cur.value = val;
                node_update(cur);
                return cur;
            }

            // 既に部分木管理ノードが存在するときの処理
            import std.algorithm : swap;

            long mid = (l + r) / 2;
            if (idx < mid) {
                // 今いる人を押しのける
                if (cur.index < idx) { swap(cur.value, val); swap(cur.index, idx); }
                cur.left = internal_set(cur.left, idx, val, l, mid);
            }
            else {
                if (idx < cur.index) { swap(cur.value, val); swap(cur.index, idx); }
                cur.right = internal_set(cur.right, idx, val, mid, r);
            }

            node_update(cur);
            return cur;
        }

        T internal_get (const node *cur, long idx, long l, long r) {
            if (cur == null) return e();
            if (cur.index == idx) return cur.value;

            long mid = (l + r) / 2;
            if (idx < mid) return internal_get(cur.left, idx, l, mid);
            return internal_get(cur.right, idx, mid, r);
        }

        // [a, b) = 要求区間
        T internal_prod (const node *cur, long a, long b, long l, long r) {
            if (cur == null || b <= l || r <= a) return e();
            if (a <= l && r <= b) return cur.product;

            long mid = (l + r) / 2;
            T res = internal_prod(cur.left, a, b, l, mid);
            if (a <= cur.index && cur.index < b) res = op(res, cur.value);
            res = op(res, internal_prod(cur.right, a, b, mid, r));
            return res;
        }
}

import std.traits : isIntegral;
import std.int128 : Int128;

class NoTrueRangeException: Exception {
    import std.exception: basicExceptionCtors;
    mixin basicExceptionCtors;
}

class BsearchException: Exception {
    import std.exception: basicExceptionCtors;
    mixin basicExceptionCtors;
}

struct BsearchResult (T) {
    import std.format: format;

    private bool has_value = true;
    private T l, r;
    private T _value;

    this (T _l, T _r) {
        this.l = _l;
        this.r = _r;
        this.has_value = false;
    }
    this (T _l, T _r, T _value) {
        this.l = _l;
        this.r = _r;
        this._value = _value;
    }

    bool empty () {
        return !this.has_value;
    }

    T value () {
        if (this.empty()) {
            throw new NoTrueRangeException(
                    format("No true condition found in the range [%s, %s].", l, r));
        }

        return _value;
    };
}

BsearchResult!T bsearch (alias func, T) (T l, T r)
if ((isIntegral!(T) || is(T == Int128)) &&
        !is(T == byte) &&
        !is(T == ubyte) &&
        !is(T == short) &&
        !is(T == ushort))
{
    import std.traits : isCallable, ReturnType, Parameters;
    import std.meta : AliasSeq;

    static assert(isCallable!(func));
    static assert(is(ReturnType!(func) == bool));
    static assert(is(Parameters!(func) == AliasSeq!(T)));

    import std.algorithm.comparison : min, max;
    T L = l, R = r;

    if (l == r) {
        if (func(l)) return BsearchResult!(T)(L, R, l);
        return BsearchResult!(T)(L, R);
    }

    while (min(l, r) + 1 < max(l, r)) {
        T m = midpoint(l, r);

        if (func(m)) {
            l = m;
        }
        else {
            r = m;
        }
    }

    bool lb = func(l);
    if (!lb) return BsearchResult!(T)(L, R);

    bool rb = func(r);
    if (rb) return BsearchResult!(T)(L, R, r);
    if (!rb) return BsearchResult!(T)(L, R, l);

    throw new BsearchException(format("This code path should never be reached. l: %s, r: %s.", L, R));
}

T midpoint (T) (T a, T b)
if (isIntegral!(T) || is(T == Int128))
{
    static if (is(T == short) || is(T == ushort) || is(T == byte) || is(T == ubyte)) {
        import std.conv : to;
        int x = a, y = b;
        return midpoint(x, y).to!(T);
    }
    else {
        import std.math.algebraic : abs;
        import std.algorithm.comparison : min, max;
        
        int as = (0 <= a) ? 1 : -1, bs = (0 <= b) ? 1 : -1;
        if (as == bs) {
            if (as == 1) {
                return min(a, b) + (max(a, b) - min(a, b)) / 2;
            }
            return max(a, b) + (min(a, b) - max(a, b)) / 2;
        }

        return (a + b) / 2;
    }
}