結果

問題 No.686 Uncertain LIS
ユーザー gew1fw
提出日時 2025-06-12 16:41:11
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 667 bytes
コンパイル時間 193 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 109,312 KB
最終ジャッジ日時 2025-06-12 16:41:17
合計ジャッジ時間 4,925 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    intervals = []
    index = 1
    for _ in range(N):
        L = int(data[index])
        R = int(data[index + 1])
        intervals.append((L, R))
        index += 2
    
    dp = []
    for L, R in intervals:
        k = bisect.bisect_left(dp, R)
        if k == 0:
            a = L
        else:
            a = max(L, dp[k-1] + 1)
        if a > R:
            continue
        if k < len(dp):
            if a < dp[k]:
                dp[k] = a
        else:
            dp.append(a)
    print(len(dp))

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