7246 : Upper Bound
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
Upper Bound는 정렬된 배열에서 특정 값 $x$보다 큰 첫 번째 원소의 위치를 찾는 연산입니다.
Lower Bound와의 차이: Lower Bound는 $x$ 이상, Upper Bound는 $x$ 초과인 원소를 찾습니다.
주어진 $Q$개의 질의에 대해 각각의 Upper Bound를 0-based 인덱스로 출력하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
Lower Bound와의 차이: Lower Bound는 $x$ 이상, Upper Bound는 $x$ 초과인 원소를 찾습니다.
주어진 $Q$개의 질의에 대해 각각의 Upper Bound를 0-based 인덱스로 출력하십시오.
[제약 조건]
• 입력되는 모든 수는 정수입니다.
입력 설명
첫째 줄에 정렬된 정수 배열의 크기 $N$과 질의 개수 $Q$가 주어집니다. ($1 \le N, Q \le 100{,}000$)
둘째 줄에 오름차순 정렬된 $N$개의 정수가 주어집니다.
셋째 줄에 $Q$개의 질의 값 $x$가 공백으로 구분되어 주어집니다.
둘째 줄에 오름차순 정렬된 $N$개의 정수가 주어집니다.
셋째 줄에 $Q$개의 질의 값 $x$가 공백으로 구분되어 주어집니다.
출력 설명
각 질의에 대해 $x$보다 큰 첫 번째 원소의 인덱스(0-based)를 한 줄에 출력합니다.
모든 원소가 $x$보다 작거나 같으면 $N$을 출력합니다.
모든 원소가 $x$보다 작거나 같으면 $N$을 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
6 4
1 3 5 7 9 11
0 5 9 12
출력 예시
COPY
복사되었습니다!
복사되었습니다!
0
3
5
6도움
Python의
bisect.bisect_right(arr, x)가 Upper Bound를 반환합니다. 직접 구현 시 조건을 arr[mid] > x로 변경합니다.