Day 169-Q2 — 2026-10-04 | 4 乗コストの最寄り給油所（SMAWK で Monge 行列の全行の最小を O(N+M)）

📋 コピーimport sys


def smawk(rows, cols, f):
    # f(i, j) が全単調（各行の最も左の最小の列が行とともに増える）な行列の、各行の最も左の最小の列を返す
    res = {}

    def rec(rows, cols):
        if not rows:
            return
        # REDUCE: 列を行数以下に減らす（どの行の最も左の最小にもならない列を捨てる）
        st = []
        for c in cols:
            while st:
                r = rows[len(st) - 1]
                if f(r, st[-1]) > f(r, c):
                    st.pop()
                else:
                    break
            if len(st) < len(rows):
                st.append(c)
        # 偶数番目（0 始まりで奇数添字）の行だけを再帰で解く
        rec(rows[1::2], st)
        # INTERPOLATE: 残りの行は、上下の行の答えの間だけを探す
        pos = {c: k for k, c in enumerate(st)}
        k = 0
        for i in range(0, len(rows), 2):
            r = rows[i]
            hi = pos[res[rows[i + 1]]] if i + 1 < len(rows) else len(st) - 1
            best_c = st[k]
            best_v = f(r, best_c)
            while k < hi:
                k += 1
                v = f(r, st[k])
                if v < best_v:
                    best_v = v
                    best_c = st[k]
            res[r] = best_c
            k = hi

    rec(list(rows), list(cols))
    return res


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    x = [int(v) for v in data[2:2 + n]]
    y = [int(v) for v in data[2 + n:2 + n + m]]
    b = [int(v) for v in data[2 + n + m:2 + n + 2 * m]]

    def f(i, j):
        d = x[i] - y[j]
        d *= d
        return b[j] + d * d

    res = smawk(range(n), range(m), f)
    out = []
    for i in range(n):
        j = res[i]
        out.append(f"{f(i, j)} {j + 1}")
    sys.stdout.write("\n".join(out) + "\n")


main()