結果

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

ソースコード

diff # 

import bisect

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

tails = []
for L, R in intervals:
    if not tails:
        tails.append(L)
        continue
    # Binary search for the largest j where max(tails[j] + 1, L) <= R
    low = 0
    high = len(tails) - 1
    result = -1
    while low <= high:
        mid = (low + high) // 2
        x_candidate = max(tails[mid] + 1, L)
        if x_candidate <= R:
            result = mid
            low = mid + 1
        else:
            high = mid - 1
    if result != -1:
        x = max(tails[result] + 1, L)
        if result + 1 == len(tails):
            tails.append(x)
        else:
            if x < tails[result + 1]:
                tails[result + 1] = x
    else:
        if L < tails[0]:
            tails[0] = L

print(len(tails))
0