結果

問題 No.1557 Binary Variable
コンテスト
ユーザー koheijkt
提出日時 2026-02-15 19:31:38
言語 PyPy3
(7.3.17)
結果
AC  
実行時間 923 ms / 2,000 ms
コード長 1,022 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 218 ms
コンパイル使用メモリ 82,392 KB
実行使用メモリ 269,704 KB
最終ジャッジ日時 2026-02-15 19:32:05
合計ジャッジ時間 26,943 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import defaultdict
N, M = map(int, input().split())
LR = []
nums = set()
for i in range(M):
    l, r = map(int, input().split())
    LR.append((l, r))
    nums.add(l)
    nums.add(r)

zaatsu = {}
id = 0
for num in sorted(nums):
    zaatsu[num] = id
    id += 1

# 読み替え
LR2 = []
in_events = defaultdict(list)
out_events = defaultdict(list)
for i in range(M):
    l, r = LR[i]
    l2, r2 = zaatsu[l], zaatsu[r]
    in_events[l2].append(i)
    out_events[r2].append(i)

cnt = 0
que = []
done = [False] * M
for i in range(0, 2*M + 1):
    # 受け入れ
    for idx in in_events[i]:
        que.append(idx)
    
    # このタイミングで串を指す必要があるか判断
    flag = False
    for idx in out_events[i]:
        if done[idx]:
            continue
        flag = True

    if flag:
        cnt += 1
        # que に入ってるやつらを done にする
        while que:
            target = que.pop()
            done[target] = True
#print(done, cnt)
ans = N - cnt
print(ans)
0