結果

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

ソースコード

diff # 

import bisect

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

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