ABC294Dを解いた【SortedSet】

筆者はレート800前後の茶～緑コーダ

ABC294のD問題を解いていく

実装コード

N人をキューに格納

• イベント1で呼ばれたらその人をSortedSetに格納
• イベント2で受付に行った人はSortedSetから削除
• イベント3でSortedSetの最小値を回答

main.py

from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, Counter, deque
from functools import reduce, lru_cache
from itertools import product, accumulate, groupby, combinations
import sys
import os
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
IS_LOCAL = int(os.getenv("ATCODER", "0"))==0
err = (lambda *args, **kwargs: print(*args, **kwargs, file=sys.stderr)) if IS_LOCAL else (lambda *args, **kwargs: None)

from sortedcontainers import SortedSet

def main():
    N, Q = rLI()
    u = deque(range(1,N+1))
    s = SortedSet()
    for _ in range(Q):
        e = rLI()
        
        if e[0] == 1:
            i = u.popleft()
            s.add(i)
        elif e[0] == 2:
            i = e[1]
            s.remove(i)
        elif e[0] == 3:
            i = s[0]
            print(i)

if __name__ == '__main__':
    main()

感想

解説見る前に呼ばれた人の管理にセグ木使っちゃった。
一応その実装でACしたけど、解説みたらSortedSetで良かったのでとき直した。