結果

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

ソースコード

diff # 

import bisect

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    N = int(data[0])
    idx = 1
    ranges = []
    for _ in range(N):
        L = int(data[idx])
        R = int(data[idx+1])
        ranges.append((L, R))
        idx += 2
    
    tails = []
    for L, R in ranges:
        left = bisect.bisect_left(tails, R)
        j = left - 1
        
        if j >= 0:
            if len(tails) == 0:
                pass
            else:
                if L > tails[j]:
                    x = L
                else:
                    x = tails[j] + 1
                if x > R:
                    continue
                if j + 1 >= len(tails):
                    tails.append(x)
                else:
                    if x < tails[j+1]:
                        tails[j+1] = x
        else:
            if len(tails) == 0:
                tails.append(L)
            else:
                x = L
                if x < tails[0]:
                    tails[0] = x
    print(len(tails))

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