문제 1020 · 기초 3
로그 구간 조회
이분 탐색 · 정렬
테스트별 제한 2000ms · 브라우저 채점
문제
하루치 접속 로그 N줄에서 시각만 뽑아 놓았다. 시각은 자정부터 지난 초(0 ~ 86,399)로 적혀 있고 순서가 뒤섞여 있다. 같은 시각이 여러 번 나올 수 있다. 질문 Q개에 답하라. 각 질문은 두 시각 a, b 로 이루어지며, a 초 이상 b 초 이하에 찍힌 로그가 몇 줄인지 묻는다.
입력
첫째 줄에 N 과 Q 가 주어진다. (1 ≤ N, Q ≤ 30,000) 둘째 줄에 로그 시각 N개가 주어진다. 다음 Q개 줄에 a 와 b 가 주어진다. (0 ≤ a ≤ b ≤ 86,399)
출력
질문마다 한 줄에 답을 출력한다.
예제 입력 1
6 3 300 10 3600 10 59 86399 10 59 0 9 60 86399
예제 출력 1
3 0 3
힌트 펼치기
- 시각을 정렬해 두면 'b 이하인 것의 개수 − a 미만인 것의 개수' 가 답이다.
- 정렬된 배열에서 'x 미만인 것의 개수' 는 이분 탐색으로 구한다. (Python: bisect 모듈)
관련 장
풀이 작성
코드는 서버로 전송하지 않습니다. 테스트가 공개되는 연습용 채점으로, 대회·인증용이 아닙니다.
풀이를 제출하면 여기에서 결과를 확인할 수 있습니다.
로그인 여부와 관계없이 이 브라우저에만 최근 제출 50개를 저장합니다.