結果
問題 | 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_leftN,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] + uniondic[L] = (L,R)continuen = Noneif 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]] = nelif ind == len(union):l,r = dic[union[ind-1]]if r < L:union.append(L)dic[L] = (L,R)continueelif 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]] = nelse:l,r = dic[union[ind-1]]n = Noneif r < L:l,r = dic[union[ind]]if R < l:union = [L] + uniondic[L] = (L,R)continuen = Noneif 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]] = ncontinueelif 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))