#1144689 (D) No.2333 Slime Structure

• 問題: No.2333 Slime Structure
• ユーザー: InTheBloom
• 提出日時: 2026-01-13 20:37:29
• 言語: D (dmd 2.111.0)
• 結果: WA
• 実行時間: -
• コード長: 11,510 bytes
• コンパイル時間: 3,975 ms
• コンパイル使用メモリ: 234,520 KB
• 実行使用メモリ: 56,400 KB
• 最終ジャッジ日時: 2026-01-13 20:37:54
• 合計ジャッジ時間: 24,428 ms
• ジャッジサーバーID （参考情報）: judge2 / judge6

ファイルパターン	結果
sample	AC * 2
other	WA * 31

ソースコード

import std;

void main () {
    int N = readln.chomp.to!int;
    auto A = new int[](N);
    auto B = new int[](N);
    foreach (i; 0 .. N) {
        readln.read(A[i], B[i]);
    }
    int Q = readln.chomp.to!int;
    auto t = new int[](Q);
    auto arg1 = new long[](Q);
    auto arg2 = new long[](Q);
    foreach (i; 0 .. Q) {
        readln.read(t[i], arg1[i], arg2[i]);
    }

    auto points = new RedBlackTree!(Tuple!(long, int), "a[0] < b[0]", true)();
    foreach (i; 0 .. Q) {
        if (t[i] == 1) {
            points.insert(tuple(arg1[i], i));
        }
    }

    auto blocks = new Tuple!(long, long, int)[](0);
    int[int] q1;
    // (left, right, 区間id)
    long left = 1;
    foreach (i; 0 .. N) {
        long right = left + B[i] - 1;
        while (!points.empty() && points.front()[0] <= right) {
            long p = points.front()[0];
            int qid = points.front()[1];
            points.removeFront();

            if (left < p) {
                blocks ~= tuple(left, p - 1, i);
            }

            blocks ~= tuple(p, p, i);
            q1[qid] = cast(int)(blocks.length - 1);
            while (!points.empty() && points.front()[0] == p) {
                q1[points.front()[1]] = q1[qid];
                points.removeFront();
            }
            left = p + 1;
        }

        if (left <= right) {
            blocks ~= tuple(left, right, i);
        }
        left = right + 1;
    }

    struct M {
        long val;
        long lVal;
        long rVal;
        long acc;
        bool id = false;
        // lVal: 左端を含むmax
        // rVal: 右端を含むmax

        string toString () {
            return format("%s %s %s %s %s", val, lVal, rVal, acc, id ? "t" : "f");
        }
    }
    M op (M a, M b) {
        if (a.id) {
            return b;
        }
        if (b.id) {
            return a;
        }

        auto ret = M();
        ret.val = max(a.val, b.val);
        ret.val = max(ret.val, a.rVal + b.lVal);
        ret.lVal = max(a.lVal, a.acc + b.lVal);
        ret.rVal = max(b.rVal, a.rVal + b.acc);
        ret.acc = a.acc + b.acc;
        return ret;
    }
    M e () {
        return M(0, 0, 0, 0, true);
    }

    auto seg = new SegmentTree!(M, op, e)(blocks.length);
    foreach (i, bl; blocks) {
        long len = bl[1] - bl[0] + 1;
        int v = A[bl[2]];
        long acc = 1L * len * v;
        long val = 0 <= v ? acc : v;
        long lVal = val;
        long rVal = val;

        seg.set(i, M(val, lVal, rVal, acc));
    }

    auto bkSize = blocks.map!(x => x[1] - x[0] + 1).array;
    auto bkAcc = new long[](bkSize.length + 1);
    foreach (i; 0 .. bkSize.length) {
        bkAcc[i + 1] = bkAcc[i] + bkSize[i];
    }

    auto NA = A.dup;
    auto ans = new long[](0);
    foreach (i; 0 .. Q) {
        if (t[i] == 1) {
            int v = cast(int)(arg2[i]);
            seg.set(q1[i], M(v, v, v, v));
            NA[blocks[q1[i]][2]] = v;
        }

        if (t[i] == 2) {
            long L = arg1[i];
            long R = arg2[i];
            bool fl (int x) {
                return L <= bkAcc[x];
            }
            bool fr (int x) {
                return R <= bkAcc[x];
            }

            // leftとrightがそれぞれどのブロックに含まれるか
            int li = bsearch!(fl)(cast(int)(bkAcc.length - 1), 0).value - 1;
            int ri = bsearch!(fr)(cast(int)(bkAcc.length - 1), 0).value - 1;

            if (li == ri) {
                long len = R - L + 1;
                int v = NA[blocks[li][2]];
                if (0 <= v) {
                    ans ~= v * len;
                }
                else {
                    ans ~= v;
                }
                continue;
            }

            // 左モノイド
            auto lm = M();
            {
                long len = blocks[li][1] - L + 1;
                int v = NA[blocks[li][2]];
                lm.acc = 1L * len * v;
                lm.val = 0 <= v ? lm.acc : v;
                lm.lVal = lm.val;
                lm.rVal = lm.val;
            }

            // 右モノイド
            auto rm = M();
            {
                long len = R - blocks[ri][0] + 1;
                int v = NA[blocks[ri][2]];
                rm.acc = 1L * len * v;
                rm.val = 0 <= v ? rm.acc : v;
                rm.lVal = rm.val;
                rm.rVal = rm.val;
            }

            auto mm = seg.prod(li + 1, ri);

            ans ~= op(op(lm, mm), rm).val;
        }
    }

    writefln("%(%s\n%)", 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 SegmentTree (T, alias ope, alias e)
if (
           isCallable!(ope)
        && isCallable!(e)
        && is (ReturnType!(ope) == T)
        && is (ReturnType!(e) == T)
        && is (Parameters!(ope) == AliasSeq!(T, T))
        && is (Parameters!(e) == AliasSeq!())
        )
{
    /* 内部の配列が1-indexedで2冪のセグメントツリー */
    import std.format : format;
    T[] X;
    size_t length;

    /* --- Constructors --- */
    this (size_t length_) {
        adjust_array_length(length_);
        for (size_t i = length; i < 2*length; i++) {
            X[i] = e();
        }
        build();
    }

    import std.range.primitives : isInputRange;
    this (R) (R Range)
    if (isInputRange!(R) && is (ElementType!(R) == T))
    {
        adjust_array_length(walkLength(Range));
        size_t i = length;
        foreach (item; Range) {
            X[i] = item;
            i++;
        }
        while (i < 2*length) { X[i] = e(); i++; }
        build();
    }

    /* --- Functions --- */
    private 
        void adjust_array_length (size_t length_) {
            length = 1;
            while (length <= length_) length *= 2;
            X = new T[](2*length);
        }

        void set_with_no_update (size_t idx, T val)
        in {
            assert(idx < length,
                    format("In function \"set_with_no_update\", idx is out of range. (length = %s idx = %s)", length, idx));
        }
        do {
            X[length+idx] = val;
        }

        void build () {
            for (size_t i = length-1; 1 <= i; i--) {
                X[i] = ope(X[2*i], X[2*i+1]);
            }
        }

    public
        override string toString () {
            string res = "";
            int level = 1;
            while ((2^^(level-1)) < X.length) {
                res ~= format("level: %2s | ", level);
                for (size_t i = (2^^(level-1)); i < (2^^level); i++) {
                    res ~= format("%s%s", X[i], (i == (2^^level)-1 ? "\n" : " "));
                }
                level++;
            }
            return res;
        }

        void set (size_t idx, T val)
        in {
            assert(idx < length,
                    format("In function \"set\", idx is out of range. (length = %s idx = %s)", length, idx));
        }
        do {
            idx += length;
            X[idx] = val;
            while (2 <= idx) {
                idx /= 2;
                X[idx] = ope(X[2*idx], X[2*idx+1]);
            }
        }

        T get (size_t idx)
        in {
            assert(idx < length,
                    format("In function \"get\", idx is out of range. (length = %s idx = %s)", length, idx));
        }
        do {
            idx += length;
            return X[idx];
        }

        T prod (size_t l, size_t r)
        in {
            assert(l < length,
                    format("In function \"prod\", l is out of range. (length = %s l = %s)", length, l));
            assert(r <= length,
                    format("In function \"prod\", r is out of range. (length = %s r = %s)", length, r));
            assert(l <= r,
                    format("In function \"prod\", l < r must be satisfied. (length = %s l = %s, r = %s)", length, l, r));
        }
        do {
            /* Returns all prod O(1) */
            if (l == 0 && r == length) return X[1];
            if (l == r) return e();

            /* Closed interval [l, r] */
            r--;
            l += length, r += length;
            T LeftProd, RightProd;
            LeftProd = RightProd = e();

            while (l <= r) {
                if (l % 2 == 1) {
                    LeftProd = ope(LeftProd, X[l]);
                    l++;
                }
                if (r % 2 == 0) {
                    RightProd = ope(X[r], RightProd);
                    r--;
                }

                l /= 2;
                r /= 2;
            }

            return ope(LeftProd, RightProd);
        }
}

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