回答編集履歴
3
ライブラリを見つけたので追記
test
CHANGED
|
@@ -35,3 +35,25 @@
|
|
|
35
35
|
```
|
|
36
36
|
|
|
37
37
|
それ以外にも、[公式の解説](https://atcoder.jp/contests/abc294/editorial/6005)で説明されている「解法 2 (線形時間で解く方法)」をPythonで実装する方法もあります。
|
|
38
|
+
|
|
39
|
+
#### 追記
|
|
40
|
+
|
|
41
|
+
AtCoderだと、sortedcontainers というライブラリが使えるそうです。([atcoder新ジャッジのpypy3.10で入っているライブラリたちを確認](https://qiita.com/flour/items/e1a690c6b1c0a8b5c4b6#sortedcontainers)より)
|
|
42
|
+
こちらでもACできることを確認しました。
|
|
43
|
+
|
|
44
|
+
```python
|
|
45
|
+
from sortedcontainers import SortedList
|
|
46
|
+
import heapq
|
|
47
|
+
n,q=map(int,input().split())
|
|
48
|
+
l1=SortedList()
|
|
49
|
+
l0=list(range(1,n+1))
|
|
50
|
+
for j in range(q):
|
|
51
|
+
a=input().split()
|
|
52
|
+
if a[0]=="1":
|
|
53
|
+
x=heapq.heappop(l0)
|
|
54
|
+
l1.add(x)
|
|
55
|
+
elif a[0]=="3":
|
|
56
|
+
print(l1[0])
|
|
57
|
+
else:
|
|
58
|
+
l1.remove(int(a[1]))
|
|
59
|
+
```
|
2
文言変更
test
CHANGED
|
@@ -1,5 +1,5 @@
|
|
|
1
1
|
TLE の理由については、コメントで Zuishin さんがおっしゃっている通りで、set の min が遅いからです。
|
|
2
|
-
より詳しくは、「[特集！知らないと損をする計算量の話](https://qiita.com/drken/items/18b3b3db5735241465ef)」を参照してください。同ページの「[3-4. 様々な言語での事情](https://qiita.com/drken/items/18b3b3db5735241465ef#3-4-%E6%A7%98%E3%80%85%E3%81%AA%E8%A8%80%E8%AA%9E%E3%81%A7%E3%81%AE%E4%BA%8B%E6%83%85)」に、
|
|
2
|
+
より詳しくは、「[特集！知らないと損をする計算量の話](https://qiita.com/drken/items/18b3b3db5735241465ef)」を参照してください。同ページの「[3-4. 様々な言語での事情](https://qiita.com/drken/items/18b3b3db5735241465ef#3-4-%E6%A7%98%E3%80%85%E3%81%AA%E8%A8%80%E8%AA%9E%E3%81%A7%E3%81%AE%E4%BA%8B%E6%83%85)」に、様々なデータ構造における計算量がまとめられています。
|
|
3
3
|
|
|
4
4
|
解決方法については、コメントで伝えた「[【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】](https://qiita.com/nebocco/items/638da118cd621d2628d1)」を参照してください。試しに、同ページの「[解決法3: 優先度付きキュー](https://qiita.com/nebocco/items/638da118cd621d2628d1#%E8%A7%A3%E6%B1%BA%E6%B3%953-%E5%84%AA%E5%85%88%E5%BA%A6%E4%BB%98%E3%81%8D%E3%82%AD%E3%83%A5%E3%83%BC)」からコードを(変数名だけ変えて)コピペして、`l1`の代わりにそちらを使ったところ、ACになりました。
|
|
5
5
|
```python
|
1
コメントで言及済みであることを明示
test
CHANGED
|
@@ -1,4 +1,7 @@
|
|
|
1
|
-
|
|
1
|
+
TLE の理由については、コメントで Zuishin さんがおっしゃっている通りで、set の min が遅いからです。
|
|
2
|
+
より詳しくは、「[特集！知らないと損をする計算量の話](https://qiita.com/drken/items/18b3b3db5735241465ef)」を参照してください。同ページの「[3-4. 様々な言語での事情](https://qiita.com/drken/items/18b3b3db5735241465ef#3-4-%E6%A7%98%E3%80%85%E3%81%AA%E8%A8%80%E8%AA%9E%E3%81%A7%E3%81%AE%E4%BA%8B%E6%83%85)」に、種々のデータ構造における計算量がまとめられています。
|
|
3
|
+
|
|
4
|
+
解決方法については、コメントで伝えた「[【Python】平衡二分木が必要な時に代わりに何とかするテク【競プロ】](https://qiita.com/nebocco/items/638da118cd621d2628d1)」を参照してください。試しに、同ページの「[解決法3: 優先度付きキュー](https://qiita.com/nebocco/items/638da118cd621d2628d1#%E8%A7%A3%E6%B1%BA%E6%B3%953-%E5%84%AA%E5%85%88%E5%BA%A6%E4%BB%98%E3%81%8D%E3%82%AD%E3%83%A5%E3%83%BC)」からコードを(変数名だけ変えて)コピペして、`l1`の代わりにそちらを使ったところ、ACになりました。
|
|
2
5
|
```python
|
|
3
6
|
import heapq
|
|
4
7
|
hp = list()
|