結果
問題 | No.1557 Binary Variable |
ユーザー |
|
提出日時 | 2021-06-25 22:54:00 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
AC
|
実行時間 | 936 ms / 2,000 ms |
コード長 | 1,978 bytes |
コンパイル時間 | 105 ms |
コンパイル使用メモリ | 13,056 KB |
実行使用メモリ | 15,708 KB |
最終ジャッジ日時 | 2024-06-25 08:47:23 |
合計ジャッジ時間 | 31,988 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 34 |
ソースコード
from bisect import bisect_left N,M = [int(i) for i in input().split()] union = [] dic = {} for _ in range(M): # print(union) # print(dic) L,R = [int(i) for i in input().split()] ind = bisect_left(union, L) if len(union) == 0: union.append(L) dic[L] = (L,R) if ind == 0: l,r = dic[union[0]] if R < l: union = [L] + union dic[L] = (L,R) continue n = None if L <= l <= R <= r: n = (l, R) elif L <= l <= r <= R: n = (l,r) union[0] = n[0] del dic[l] dic[n[0]] = n elif ind == len(union): l,r = dic[union[ind-1]] if r < L: union.append(L) dic[L] = (L,R) continue elif l <= L <= r <= R: n = (L,r) elif l <= L <= R <= r: n = (L,R) elif L <= l <= R <= r: n = (l, R) elif L <= l <= r <= R: n = (l,r) union[ind-1] = n[0] del dic[l] dic[n[0]] = n else: l,r = dic[union[ind-1]] n = None if r < L: l,r = dic[union[ind]] if R < l: union = [L] + union dic[L] = (L,R) continue n = None if l <= L <= r <= R: n = (L,r) elif l <= L <= R <= r: n = (L,R) elif L <= l <= R <= r: n = (l, R) elif L <= l <= r <= R: n = (l,r) union[ind] = n[0] del dic[l] dic[n[0]] = n continue elif l <= L <= r <= R: n = (L,r) elif l <= L <= R <= r: n = (L,R) elif L <= l <= R <= r: n = (l, R) elif L <= l <= r <= R: n = (l,r) union[ind-1] = n[0] del dic[l] dic[n[0]] = n # print(union) # print(dic) print(N-len(union))