結果

問題 No.2157 崖
コンテスト
ユーザー LyricalMaestro
提出日時 2025-03-29 17:52:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 4,845 ms / 6,000 ms
コード長 2,031 bytes
コンパイル時間 265 ms
コンパイル使用メモリ 82,320 KB
実行使用メモリ 102,352 KB
最終ジャッジ日時 2025-03-29 17:53:11
合計ジャッジ時間 23,901 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/2157

def binary_search(base_d_array, v, b):
    if v < base_d_array[0]:
        return -1

    low = (0 if b == -1 else b)
    high = len(base_d_array) - 1
    while high - low > 1:
        mid = (high + low) //2
        if base_d_array[mid] <= v:
            low = mid
        else:
            high = mid
    if base_d_array[high] <= v:
        return high
    else:
        return low
    

def solve(N, M, D, K):
    d_array = D[0]
    for i in range(1, N):
        base_d_array = d_array
        d_array = []
        for j in range(M):
            d = D[i][j]

            # 2分探索
            if d < base_d_array[0]:
                continue

            highi = binary_search(base_d_array, d, -1)
            if base_d_array[highi] >= d - K:
                d_array.append(d)

        if len(d_array) == 0:
            return False
    if len(d_array) == 0:
        return False
    
    return True


def main():
    N, M = map(int, input().split())
    D = []
    for _ in range(N):
        D.append(list(map(int, input().split())))

    # まずはソート
    for d_list in D:
        d_list.sort()
    max_size = 0
    for i in range(N - 1):
        max_size = max(max_size, D[i + 1][-1] - D[i][0], 0)

    # 座標圧縮つきBITの用意
    d_array = D[0]
    for i in range(1, N):
        base_d_array = d_array
        d_array = []
        for j in range(M):
            d = D[i][j]

            # 2分探索
            if d < base_d_array[0]:
                continue
            d_array.append(d)
        if len(d_array) == 0:
            print(-1)
            return
    if len(d_array) == 0:
        print(-1)
        return

    # 最小値を計算
    low = 0
    high = max_size
    while high - low > 1:
        mid = (high  + low) // 2
        if solve(N, M, D, mid):
            high = mid
        else:
            low = mid

    if solve(N, M, D, low):
        print(low)
    else:
        print(high)
            






if __name__ == "__main__":
    main()
0