망갤을 살려보자. 심심할때마다 글 싸야지


이 문제를 풀어보자

빈 집합 하나가 있고, 쿼리가 Q<=10000000개 주어진다. 쿼리는 2가지 종류가 있다.

1 x : 집합에 x 추가 (중복 원소가 들어갈 수 있다)

2 x : 집합에서 x 제거 (x가 집합에 존재함이 보장된다)


각 쿼리가 끝날 때마다 집합에서 최소원소를 출력해야 한다. 비어 있으면 -1을 출력한다.


이 문제는 그냥 (multi)set이나 map을 박으면 풀리는 문제이다. (풀이 : https://ideone.com/szKBF5)

그러나 set은 로그제곱에 버금가는 강력한 속도를 자랑하기 때문에 같은 복잡도라도 set을 쓰면 터지는 경우가 있다.

위 문제는 priority_queue 2개를 써서 풀 수 있다. 한번 풀어보자. (풀이 : https://ideone.com/JTFllH)