31440번 - 히스토그램에서 가장 큰 직사각형과 쿼리 2 서브태스크다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 238 | 54 | 34 | 19.209% |
문제
Study nature: 자연을 탐구하고 세상의 문제를 발견하는 인재.
위 문장은 KSA 비전 2040에서 공개된 모토의 일부다.
하지만 본 문제의 출제자는 KSA를 졸업했으므로, 남의 문제를 베껴오기로 하였다. 본 문제는 히스토그램에서 가장 큰 직사각형과 쿼리 (16977)를 베껴와 몇 글자만 바꾼 문제다.
히스토그램은 직사각형 여러 개가 아래쪽으로 정렬되어 있는 도형이다. 각 직사각형은 너비가 $1$로 일정하지만, 높이는 서로 다를 수도 있다. 예를 들어, 다음 그림은 높이가 $3, 5, 8, 8, 4, 7$인 직사각형으로 이루어진 히스토그램이다.
히스토그램에서 아래와 같은 쿼리 $Q$개를 수행해보자.
- $l \, r$: $l$번째 직사각형부터 $r$번째 직사각형까지만 있을 때, 가장 넓이가 큰 직사각형의 넓이를 출력한다.
입력
첫 번째 줄에 직사각형의 수 $N$이 주어진다.
두 번째 줄에는 히스토그램에서 각 직사각형의 높이를 나타내는 $N$개의 정수 $H_1, H_2, \cdots, H_N$가 공백으로 구분되어 왼쪽에서 오른쪽으로 순서대로 주어진다.
세 번째 줄에는 쿼리의 수 $Q$가 주어진다.
다음 $Q$개의 줄에 쿼리들의 정보가 주어지며, 각 줄에는 두 개의 정수 $l$, $r$이 공백으로 구분되어 주어진다.
출력
$Q$개의 줄에 걸쳐 각 쿼리의 정답을 출력한다.
제한
- $1\leq N,Q\leq 10^5$
- $1\leq H_i\leq 10^9$
- $1\leq l\leq r\leq N$
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | $Q \leq 300$ |
| 2 | 40 | $H_1 < H_2 < \cdots < H_N$ |
| 3 | 32 | $i\neq j \Rightarrow H_i \neq H_j$ |
| 4 | 24 | 추가 제약 조건 없음 |
예제 입력 1
6 3 5 8 8 4 7 5 1 6 1 3 2 4 3 5 4 6
예제 출력 1
20 10 16 16 12
출처
School > 한국과학영재학교 > 2024 KSA Automata Winter Contest J번
- 문제를 만든 사람: aaron0526
- 문제를 검수한 사람: eric00513, flakepowders, gs20036, hjroh0315, kiwiyou, mickeyjung, parkky, shiftpsh, utilforever, vkdldjvkdnj, wizardrabbit
채점 및 기타 정보
- 예제는 채점하지 않는다.
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호