結果

問題 No.686 Uncertain LIS
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 21:41:36
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 858 bytes
コンパイル時間 139 ms
コンパイル使用メモリ 82,268 KB
実行使用メモリ 109,048 KB
最終ジャッジ日時 2025-06-12 21:45:22
合計ジャッジ時間 4,819 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 WA * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    ranges = []
    for _ in range(N):
        L = int(data[idx])
        R = int(data[idx+1])
        ranges.append((L, R))
        idx += 2
    
    dp = []
    for L, R in ranges:
        if not dp:
            x = L
            dp.append(x)
        else:
            m = dp[-1]
            x_candidate = m + 1
            optimal_x = max(L, x_candidate)
            if optimal_x <= R:
                dp.append(optimal_x)
            else:
                x = L
                pos = bisect.bisect_left(dp, x)
                if pos < len(dp) and x < dp[pos]:
                    dp[pos] = x
                elif pos == 0:
                    dp[0] = x
    print(len(dp))

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