#1169921 (D) No.2332 Make a Sequence

• 問題: No.2332 Make a Sequence
• ユーザー: InTheBloom
• 提出日時: 2026-07-01 13:31:19
• 言語: D (dmd 2.112.0)
• 結果: WA
• 実行時間: -
• コード長: 5,785 bytes
• コンパイル時間: 2,582 ms
• コンパイル使用メモリ: 171,832 KB
• 実行使用メモリ: 36,744 KB
• 最終ジャッジ日時: 2026-07-01 13:31:43
• 合計ジャッジ時間: 21,412 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_1

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

ソースコード

import std;

void main () {
    int N, M;
    readln.read(N, M);
    auto A = readln.split.to!(int[]);
    auto B = readln.split.to!(int[]);
    auto C = readln.split.to!(int[]);

    auto AB = A ~ B;
    auto z = zAlgorithm(A ~ B);
    auto up = z[N .. N + M];

    auto cht = new LiChaoTree(iota(M + 1).array);
    auto dp = new long[](M + 1);
    dp[0] = 0;
    cht.addLineSegment(0, 0 + up[0] + 1, C[0], dp[0] - 0 * C[0]);
    foreach (i; 1 .. M + 1) {
        dp[i] = cht.getPoint(i);
        if (i < M) {
            cht.addLineSegment(i, i + up[i] + 1, C[i], dp[i] - 1L * i * C[i]);
        }
    }

    long ans = dp[M];
    if (ans == long.max) {
        writeln(-1);
    }
    else {
        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));
    }
}

int[] zAlgorithm (T) (const T[] S) {
    const int N = cast(int) S.length;
    auto ret = new int[](N);
    if (N == 0) {
        return ret;
    }
    ret[0] = N;

    int i = 1, j = 1;
    // S[0 .. j - i) = S[i .. j)を保つ。

    while (i < N) {
        if (j < i) {
            j = i;
        }

        // LCPを広げる。
        while (j < N) {
            if (S[j - i] != S[j]) {
                break;
            }
            j++;
        }
        ret[i] = j - i;

        // 計算を再利用する。
        int k = 1;
        while (k <= i && i + k < j && i + k + ret[k] < j) {
            ret[i + k] = ret[k];
            k++;
        }

        i += k;
    }

    return ret;
}

class LiChaoTree {
    import std.algorithm;
    import std.array;
    import std.traits;
    import std.exception;

    alias Integer = long;
    struct Line {
        // y = ax + b
        Integer a, b;
    }
    struct CRange {
        // [l, r]
        int l, r;
    }

    Line[] line;
    CRange[] range;
    int leafs;
    long[] coords;

    this (T) (const T[] coords_) 
        if (isImplicitlyConvertible!(T, long)) {
        coords = coords_.map!(v => cast(long)(v)).array;

        coords = coords.sort.uniq.array;
        leafs = 1;
        while (leafs < coords.length) {
            leafs *= 2;
        }

        // 評価点側も2冪に合わせる
        int rem = leafs - cast(int)(coords.length);
        long dval = (coords.length == 0 ? 0L : coords[$ - 1]);
        foreach (_; 0 .. rem) {
            coords ~= dval;
        }

        line = new Line[](2 * leafs);
        line[] = Line(0, Integer.max);
        range = new CRange[](2 * leafs);
        foreach (i; 0 .. leafs) {
            range[leafs + i] = CRange(i, i);
        }
        foreach_reverse (i; 1 .. leafs) {
            range[i].l = range[2 * i].l;
            range[i].r = range[2 * i + 1].r;
        }
    }

    private void add (int rootId, Integer a, Integer b) {
        Line li = line[rootId];
        int l = range[rootId].l, r = range[rootId].r;
        int m = (l + r) / 2;

        long lpv = li.a * coords[l] + li.b;
        long mpv = li.a * coords[m] + li.b;
        long rpv = li.a * coords[r] + li.b;

        long lnv = a * coords[l] + b;
        long mnv = a * coords[m] + b;
        long rnv = a * coords[r] + b;

        // 全域で優れている
        if (lnv < lpv && rnv < rpv) {
            line[rootId] = Line(a, b);
            return;
        }
        // 全域で劣っている
        if (lpv <= lnv && rpv <= rnv) {
            return;
        }

        // 直線swap
        if ((lnv < lpv && mnv < mpv) || (mnv < mpv && rnv < rpv)) {
            line[rootId] = Line(a, b);
            swap(li.a, a);
            swap(li.b, b);
            swap(lpv, lnv);
            swap(mpv, mnv);
            swap(rpv, rnv);
        }

        if (lnv < lpv) {
            add(2 * rootId, a, b);
        }
        else {
            add(2 * rootId + 1, a, b);
        }
    }

    void addLine (Integer a, Integer b) {
        add(1, a, b);
    }

    // [l, r)
    void addLineSegment (long l, long r, Integer a, Integer b) {
        enforce(l <= r);
        if (l == r) {
            return;
        }
        if (coords[$ - 1] < l || r <= coords[0]) {
            return;
        }

        // 点の探索
        int lo = -1, hi = cast(int)(coords.length) - 1;
        while (1 < hi - lo) {
            int m = (hi + lo) / 2;
            if (l <= coords[m]) {
                hi = m;
            }
            else {
                lo = m;
            }
        }
        int L = hi;

        lo = 0, hi = cast(int)(coords.length);
        while (1 < hi - lo) {
            int m = (hi + lo) / 2;
            if (coords[m] < r) {
                lo = m;
            }
            else {
                hi = m;
            }
        }
        int R = lo;

        if (R < L) {
            return;
        }

        // セグメントの探索
        // [L, R]
        L += leafs;
        R += leafs;

        while (L <= R) {
            if (L % 2 == 1) {
                add(L, a, b);
                L++;
            }
            if (R % 2 == 0) {
                add(R, a, b);
                R--;
            }

            L /= 2;
            R /= 2;
        }
    }

    long getPoint (long p) {
        int lo = 0, hi = cast(int)(coords.length);
        while (1 < hi - lo) {
            int m = (hi + lo) / 2;
            if (coords[m] <= p) {
                lo = m;
            }
            else {
                hi = m;
            }
        }
        enforce(coords[lo] == p);

        int cur = lo + leafs;
        long ret = long.max;
        while (0 < cur) {
            long val = p * line[cur].a + line[cur].b;
            ret = min(ret, val);
            cur /= 2;
        }
        return ret;
    }
}