結果

問題 No.2157 崖
コンテスト
ユーザー isee
提出日時 2022-12-09 22:03:40
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 6,385 bytes
コンパイル時間 481 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 115,912 KB
最終ジャッジ日時 2024-10-14 22:00:48
合計ジャッジ時間 10,196 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 10 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = lambda: sys.stdin.readline().rstrip()

class SegTree:
    '''セグメント木
    概要:
        要素数 N で
            ・値の更新
            ・範囲 [l,r) での演算
        が 1回 O(logN) でできる
        演算がモノイド(結合法則・単位元)ならいける
    '''

    def __init__(self, list, op, E):
        '''初期化 SegTree(初期値, 演算, 単位元) O(N)
        使い方:
            SegTree(list, min, INF)
            SegTree(list, (lambda x,y:x+y), 0)
            def add(x,y):
                return x+y
            SegTree(list, add, 0)
            など
        Args:
            list (list): 初期値のリスト
            op (func): 用いる演算
            E (***): 単位元
        Returns:
            void
        '''
        self.N = len(list)  # 実際の要素数
        self.op = op  # 演算
        self.E = E  # 単位元
        self.log = (self.N - 1).bit_length()  # 木の高さ
        self.size = 1 << self.log  # 作りやすさのためサイズを2の冪乗に
        self.d = [E for _ in range(2 * self.size)]  # セグ木本体 [0]は使わない
        for i in range(self.N):
            self.d[self.size+i] = list[i]
        for i in range(self.size-1,0,-1):
            self.update(i)

    def set(self, p, x):
        '''値の更新 set(場所, 値) O(logN)
        Args:
            p (int): 値を入れるindex < N
            x (***): 入れる値
        Returns:
            void
        '''
        assert 0 <= p < self.N
        p += self.size
        self.d[p] = x
        for i in range(1, self.log+1):
            self.update(p >> i)

    def get(self, p):
        '''値の取得 get(場所) O(1)
        Args:
            p (int): 値を取得するindex < N
        Returns:
            void
        '''
        assert 0 <= p < self.N
        return self.d[p + self.size]

    def prob(self, l, r):
        '''op( [l,r) )の計算結果 prob(左, 右) O(logN)
        Args:
            l (int): 左端のindex
            r (int): 右端のindex このindexの値はop計算に含まれない
        Returns:
            ***: 計算結果 op(l, l+1, ..., r-1)
        '''
        assert 0 <= l <= r <= self.N
        suml = self.E
        sumr = self.E
        l += self.size
        r += self.size
        while l < r:
            if l % 2 == 1:
                suml = self.op(suml, self.d[l])
                l += 1
            if r % 2 == 1:
                sumr = self.op(self.d[r-1], sumr)
            l >>= 1
            r >>= 1
        return self.op(suml, sumr)

    def all_prob(self):
        '''全ての区間について計算した結果<=>prob(0, N) O(1)
        Args:
            void
        Returns:
            ***: 計算結果 op(0, 1, ..., N-1)
        '''
        return self.d[1]

    def max_right(self, L, f):
        '''f( op( [L,r) ) ) が True になる最大のrを求める O(logN)？
        使い方:
            f は 範囲が狭いほどTrue、広いほどFalseで単調なもの
            max_right(0, lambda x: x<10)
            など
        Args:
            L (int): 左端のindex
            f (func): 単調でbool値な関数
        Returns:
            int: 右端のindex
        '''
        assert 0 <= L <= self.N
        assert f(self.E)
        if L == self.N:
            return self.N
        l = L
        l += self.size
        sum = self.E
        while True:
            while l % 2 == 0:
                l >>= 1
            if not(f(self.op(sum, self.d[l]))):
                while l < self.size:
                    l = 2 * l
                    if f(self.op(sum, self.d[l])):
                        sum = self.op(sum, self.d[l])
                        l += 1
                return l - self.size
            sum = self.op(sum, self.d[l])
            l += 1
            if l & -l == l:  # 末尾まで計算してもTrue
                break
        return self.N

    def min_left(self, R, f):
        '''f( op( [l,R) ) ) が True になる最小のlを求める O(logN)？
        使い方:
            f は 範囲が狭いほどTrue、広いほどFalseで単調なもの
            max_left(10, lambda x: x<10)
            など
        Args:
            R (int): 右端のindex このindexの値はop計算に含まれない
            f (func): 単調でbool値な関数
        Returns:
            int: 左端のindex
        '''
        assert 0 <= R <= self.N
        assert f(self.E)
        if r == 0:
            return 0
        r = R
        r += self.size
        sum = self.E
        while True:
            r -= 1
            while (r > 1) and (r % 2 == 1):
                r >>= 1
            if not(f(self.op(self.d[r], sum))):
                while r < self.size:
                    r = 2 * r + 1
                    if f(self.op(self.d[r], sum)):
                        sum = self.op(self.d[r], sum)
                        r -= 1
                return r + 1 - self.size
            sum = self.op(self.d[r], sum)
            if r & -r == r:
                break
        return 0

    def update(self, k):
        '''セグ木のk番目の要素を更新
        Args:
            k (int): 更新するindex
        Returns:
            void
        '''
        self.d[k] = self.op(self.d[k * 2], self.d[k * 2 + 1])

    def __str__(self):
        return str([self.get(i) for i in range(self.N)])

import bisect # .bisect_left(list, key)

def main():
    # 入力
    N, M = map(int, input().split())
    if N == 1:
        print(0)
        return
    D = [sorted(list(set(map(int, input().split())))) for _ in range(N)]
    # 計算・出力
    ST = SegTree([0]*M, lambda x,y: min(x,y), 10**10)
    for i in range(1, N):
        dp = [10**10]*len(D[i])
        for j in range(len(D[i])):
            diff = D[i][j]
            r = bisect.bisect_right(D[i-1], diff)
            ng = -1
            ok = 10**10
            while abs(ng-ok) > 1:
                mid = (ok+ng)//2
                l = bisect.bisect_left(D[i-1], diff-mid)
                if ST.prob(l, r) <= mid : # ここ頑張る
                    ok = mid
                else:
                    ng = mid
            dp[j] = ok
        ST = SegTree(dp, lambda x,y: min(x,y), 10**10)
    ans = ST.all_prob()
    print(ans if ans != 10**10 else -1)

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