7252 : 이분탐색 + 정렬
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
정렬되지 않은 $N$개의 정수 배열과 $Q$개의 목표값이 주어질 때, 배열을 정렬한 후 이분탐색으로 각 목표값의 존재 유무를 출력하십시오.
먼저 정렬하면 각 질의를 $O(\log N)$에 처리할 수 있어 전체 시간복잡도는 $O(N \log N + Q \log N)$입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
먼저 정렬하면 각 질의를 $O(\log N)$에 처리할 수 있어 전체 시간복잡도는 $O(N \log N + Q \log N)$입니다.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 배열의 크기 $N$과 쿼리 수 $Q$가 주어집니다. ($1 \le N, Q \le 100{,}000$)
둘째 줄에 $N$개의 임의의 정수가 주어집니다.
셋째 줄부터 $Q$개의 줄에 목표값이 주어집니다.
둘째 줄에 $N$개의 임의의 정수가 주어집니다.
셋째 줄부터 $Q$개의 줄에 목표값이 주어집니다.
출력 설명
각 쿼리에 대해 목표값이 배열에 존재하면
1, 없으면 0을 한 줄에 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 3
3 1 4 1 5
1
4
6
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1
1
0도움
정렬 후
bisect_left로 삽입 위치를 구하고, 해당 위치의 값이 목표값과 같은지 비교합니다. set(arr)를 이용한 $O(1)$ 검색도 허용됩니다.