6178 : 이진탐색 트리와 힙
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
각 노드가 (키, 우선순위) 쌍을 갖습니다. 키 기준으로는 이진 탐색 트리(BST) 구조를 만족하고, 우선순위 기준으로는 최소 힙(Min Heap) 구조를 동시에 만족하는 유일한 트립(Treap)을 구성하고, 그 트리의 전위 순회(Preorder Traversal) 결과를 출력하는 프로그램을 작성하시오.
입력 설명
첫째 줄에 노드의 개수 N (1 ≤ N ≤ 100,000)이 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 각 노드의 키와 우선순위가 공백으로 구분되어 주어집니다. 모든 키와 우선순위는 고유합니다.
둘째 줄부터 N개의 줄에 걸쳐 각 노드의 키와 우선순위가 공백으로 구분되어 주어집니다. 모든 키와 우선순위는 고유합니다.
출력 설명
생성된 트립의 전위 순회한 키 목록을 공백으로 구분하여 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5
10 5
5 2
15 8
3 1
8 6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3 5 10 8 15