32961번 - 폭우 (Easy)
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 73 | 20 | 16 | 29.091% |
문제
일렬로 놓인 $N$개의 칸에 끊임없는 비가 내린다. $i$번째 칸에는 초기에 높이 $A_i$의 벽이 세워져 있다. 벽 안에 고인 비가 가득 차면 왼쪽 끝과 오른쪽 끝의 공허로 넘쳐서 사라진다. 또한, 빗물은 일렬로 놓인 좌우 방향 이외의 방향으로 이동하지 않는다.
$Q$개의 쿼리가 주어진다. 각 쿼리는 $i, x$로 이뤄지며, $i$번째 칸의 벽의 높이 $A_i$가 이후로 $x$가 된다는 의미이다. 이 때, $A_i \lt x$임이 보장된다.
각 쿼리가 끝날 때마다 최대 얼마만큼의 비가 고이게 될 수 있는지 답하라.
입력
첫 번째 줄에 $N$, $Q$가 차례대로 주어진다. ($1 \le N \le 100\,000; 1 \le Q \le 100\,000$)
두 번째 줄에 초기 높이 $A_i$가 순서대로 주어진다. ($1 \le A_i \le 10^9$)
세 번째 줄부터 $Q$개의 줄에 걸쳐 각 줄마다 쿼리를 의미하는 두 정수 $i, x$가 공백으로 구분되어 주어진다. ($1 \le i \le N; 1 \le x \le 10^9$)
입력으로 주어지는 모든 수는 정수이다.
출력
$Q$개의 줄에 걸쳐 각 쿼리를 수행했을 때의 답을 출력한다.
예제 입력 1
12 3 3 1 4 1 5 9 2 6 5 3 5 10 4 2 1 10 3 9
예제 출력 1
28 58 53
초기 상태는 다음과 같으며, $29$만큼의 물이 차있다.
#
#.....#
#.....#
#.....#
#.#...#
##.##.##
#.##.##.##
#.#.##.#####
#.#.########
############
$1$번 쿼리가 끝난 직후, 다음과 같이 $4$번째 칸에 세워진 벽의 높이가 $1$에서 $2$가 되어 $28$만큼의 물이 차있게 된다.
#
#.....#
#.....#
#.....#
#.#...#
##.##.##
#.##.##.##
#.#.##.#####
#.##########
############
$2$번 쿼리가 끝난 직후, 다음과 같이 $1$번째 칸에 세워진 벽의 높이가 $10$이 되어 $58$만큼의 물이 차있게 된다.
#..........#
#....#.....#
#....#.....#
#....#.....#
#....#.#...#
#...##.##.##
#.#.##.##.##
#.#.##.#####
#.##########
############
$3$번 쿼리가 끝난 직후, 다음과 같이 $3$번째 칸에 세워진 벽의 높이가 $9$가 되어 $53$만큼의 물이 차있게 된다.
#..........#
#.#..#.....#
#.#..#.....#
#.#..#.....#
#.#..#.#...#
#.#.##.##.##
#.#.##.##.##
#.#.##.#####
#.##########
############
출처
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호