8015 : 콘서트 티켓
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
콘서트 티켓 $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$ (고객 지불 상한 금액)
$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$이 공백으로 구분되어 주어집니다.
둘째 줄에 각 티켓의 가격 $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++의 경우
Python의 경우 세그먼트 트리 또는 Balanced BST를 구현하거나 인덱스 압축 세그먼트 트리를 사용할 수 있습니다.
std::multiset의 upper_bound를 사용하여 $t_j$를 초과하는 첫 원소의 바로 이전 원소를 찾아 출력하고 삭제(erase)하면 각 쿼리를 $O(\log N)$에 처리할 수 있습니다.Python의 경우 세그먼트 트리 또는 Balanced BST를 구현하거나 인덱스 압축 세그먼트 트리를 사용할 수 있습니다.