문제 분류 수업 진도 대회 채점현황 순위 질문게시판
게임
스도쿠 타이핑 리듬 타자게임 타이핑 테트리스 타이핑 인베이더 타이핑 지뢰찾기 8192 공룡게임 타이핑 플래피버드 랭킹
로그인

8015 : 콘서트 티켓

•시간제한: 2.000 S •메모리제한: 256 MB •제출: 0 •통과: 0 •만든사람: suakii

8015 : 콘서트 티켓

시간 2.000s · 메모리 256MB · 제출 0 · 정답 0

문제 설명

콘서트 티켓 $N$장이 있고 각각의 가격은 $h_1, h_2, \ldots, h_N$입니다.
$M$명의 고객들이 차례대로 와서 자신이 지불할 수 있는 최대 금액 $t_1, t_2, \ldots, t_M$을 제시하며 티켓을 구매하려고 합니다.
각 고객은 자신이 제시한 금액 $t_j$ 이하인 티켓 중 가격이 가장 비싼 티켓을 구매합니다. 한 번 판매된 티켓은 다시 판매할 수 없습니다.

각 고객이 구매하게 되는 티켓의 가격을 차례대로 출력하고, 구매할 수 있는 티켓이 없다면 $-1$을 출력하는 프로그램을 작성하십시오.

[제약 조건]
• $1 \le N, M \le 2 \times 10^5$
• $1 \le h_i \le 10^9$ (티켓 가격)
• $1 \le t_j \le 10^9$ (고객 지불 상한 금액)

입력 설명

첫째 줄에 두 정수 $N$과 $M$이 공백으로 구분되어 주어집니다.
둘째 줄에 각 티켓의 가격 $h_1, h_2, \ldots, h_N$이 공백으로 구분되어 주어집니다.
셋째 줄에 각 고객이 제시하는 최대 금액 $t_1, t_2, \ldots, t_M$이 공백으로 구분되어 주어집니다.

출력 설명

각 고객에 대해 구매한 티켓의 가격을 차례대로 한 줄에 하나씩 출력합니다. 구매할 수 없다면 $-1$을 출력합니다.

입력 예시
COPY
복사되었습니다!

5 3
5 3 7 8 5
4 8 3

출력 예시
COPY
복사되었습니다!

3
8
-1

도움

C++의 경우 std::multiset의 upper_bound를 사용하여 $t_j$를 초과하는 첫 원소의 바로 이전 원소를 찾아 출력하고 삭제(erase)하면 각 쿼리를 $O(\log N)$에 처리할 수 있습니다.
Python의 경우 세그먼트 트리 또는 Balanced BST를 구현하거나 인덱스 압축 세그먼트 트리를 사용할 수 있습니다.

출처/분류

NOTICE  —  BFStudy OJ 정보샘
애들아, 문제 많이 풀고 게임 잠깐 하는거지?
— 정보샘