結果

問題 No.686 Uncertain LIS
コンテスト
ユーザー lam6er
提出日時 2025-04-15 22:51:08
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 528 bytes
コンパイル時間 333 ms
コンパイル使用メモリ 82,244 KB
実行使用メモリ 88,840 KB
最終ジャッジ日時 2025-04-15 22:53:07
合計ジャッジ時間 6,388 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

import bisect

n = int(input())
intervals = [tuple(map(int, input().split())) for _ in range(n)]

dp = []
for L, R in intervals:
    if not dp:
        dp.append(L)
    else:
        pos = bisect.bisect_left(dp, R)
        k_max = pos - 1
        if k_max >= 0:
            x = max(L, dp[k_max] + 1)
        else:
            x = L
        new_length = k_max + 2
        if new_length > len(dp):
            dp.append(x)
        else:
            if x < dp[new_length - 1]:
                dp[new_length - 1] = x

print(len(dp))
0