Day 180-Q3 — 2026-10-16 | SMAWK で Monge 行列の行ごとの最小値（費用 c_j＋|x_i−y_j|³ の倉庫選び。分割統治（monotone minima）との評価回数・時間の比較つき）

📋 コピーimport sys


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    xs = list(map(int, data[2:2 + n]))
    ys = list(map(int, data[2 + n:2 + n + m]))
    cs = list(map(int, data[2 + n + m:2 + n + 2 * m]))
    ro = sorted(range(n), key=xs.__getitem__)          # 店を座標順に
    co = sorted(range(m), key=ys.__getitem__)          # 倉庫を座標順に
    X = [xs[i] for i in ro]
    Y = [ys[j] for j in co]
    Cc = [cs[j] for j in co]
    ans = [0] * n                                      # 座標順の行 i の最左最小の列

    def smawk(rows, cols):
        nr = len(rows)
        if nr == 0:
            return
        # REDUCE：どの行の最左最小にもならない列を捨て、列数を行数以下にする
        st = []
        for c in cols:
            yc, cc = Y[c], Cc[c]
            while st:
                x = X[rows[len(st) - 1]]
                t = st[-1]
                d1 = x - Y[t]
                d2 = x - yc
                if d1 < 0: d1 = -d1
                if d2 < 0: d2 = -d2
                if Cc[t] + d1 * d1 * d1 <= cc + d2 * d2 * d2:
                    break
                st.pop()
            if len(st) < nr:
                st.append(c)
        # 奇数番目の行だけで再帰
        smawk(rows[1::2], st)
        # INTERPOLATE：偶数番目の行は、上下の行の答えの間だけを見る
        k = 0
        last = st[-1]
        for t in range(0, nr, 2):
            r = rows[t]
            x = X[r]
            hi = ans[rows[t + 1]] if t + 1 < nr else last
            bc = st[k]
            d = x - Y[bc]
            if d < 0: d = -d
            best = Cc[bc] + d * d * d
            while st[k] != hi:
                k += 1
                c = st[k]
                d = x - Y[c]
                if d < 0: d = -d
                v = Cc[c] + d * d * d
                if v < best:
                    best, bc = v, c
            ans[r] = bc

    smawk(list(range(n)), list(range(m)))
    res = [0] * n
    for i in range(n):
        d = X[i] - Y[ans[i]]
        if d < 0: d = -d
        res[ro[i]] = Cc[ans[i]] + d * d * d
    sys.stdout.write("\n".join(map(str, res)) + "\n")


main()