6068 : 이중 우선순위 큐
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
이중 우선순위 큐
최솟값과 최댓값을 동시에 삭제/관리할 수 있는 이중 우선순위 큐를 구현하시오.
연산:
-
-
-
구현 힌트: 최소힙과 최대힙을 2개 병렬로 유지하고, 카운트맵(Counter)으로 동기화합니다.
모든 연산 처리 후 큐에 남은 최댓값과 최솟값을 공백으로 구분하여 출력합니다.
큐가 비어있으면 "EMPTY"를 출력합니다.
[제약 조건]
• 명령 수 $N$: $1 \le N \le 100{,}000$ (정수)
• 각 정수: $-10^9 \le x \le 10^9$ (0 제외)
최솟값과 최댓값을 동시에 삭제/관리할 수 있는 이중 우선순위 큐를 구현하시오.
연산:
-
I x: 정수 x를 큐에 삽입-
D 1: 최댓값 삭제-
D -1: 최솟값 삭제구현 힌트: 최소힙과 최대힙을 2개 병렬로 유지하고, 카운트맵(Counter)으로 동기화합니다.
모든 연산 처리 후 큐에 남은 최댓값과 최솟값을 공백으로 구분하여 출력합니다.
큐가 비어있으면 "EMPTY"를 출력합니다.
[제약 조건]
• 명령 수 $N$: $1 \le N \le 100{,}000$ (정수)
• 각 정수: $-10^9 \le x \le 10^9$ (0 제외)
입력 설명
첫째 줄에 연산의 개수 N (1 ≤ N ≤ 100,000)이 주어집니다.
다음 N개의 줄에 연산(I x, D 1, D -1)이 주어집니다.
다음 N개의 줄에 연산(I x, D 1, D -1)이 주어집니다.
출력 설명
모든 연산 처리 후 최댓값과 최솟값을 출력합니다. 큐가 비어있으면 EMPTY를 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
4
I 1
I 2
I 3
D 1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
2 1