7662 이중 우선순위 큐

최소, 최대를 둘 다 검사 가능한 이중 우선순위 큐(Priority Queue)를 구현하는 문제이다.

괜한 편법을 부렸다간 가차없이 TLE선고를 맞게 된다.
본인도 무려 41회나 틀림과 TLE를 맞고 42번째에 간신히 정답을 받았다.

이 문제를 풀기 위해선 Max Heap과 Min Heap을 둘다 구해주어야 한다.
그리고 값이 들어갈 때, 두 힙 모두 insert 해 주고, 뺄 때는 동기화를 시켜주어야 하는데,
동기화를 시켜주는 방법은 insert 하는 값에 번호를 매겨서 그 번호를 index로 가지는 check 배열을 선언한다. 이 배열은 index가 빼져서 없다면 0, 있다면 1을 나타낸다.
매 동기화 때마다 각 힙의 루트 부분을 검사하여 check 값이 0 이 나오면 제거해준다.
동기화문제가 해결 되었다면 최대값을 뺄때는 Max Heap 에서, 최소값을 뺄때는 Min Heap에서 제거해주면 된다.

소스