| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 65 | 18 | 14 | 32.558% |
일렬로 놓인 $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$개의 줄에 걸쳐 각 쿼리를 수행했을 때의 답을 출력한다.
12 3 3 1 4 1 5 9 2 6 5 3 5 10 4 2 1 10 3 9
28 58 53
초기 상태는 다음과 같으며, 29ドル$만큼의 물이 차있다.
#
#.....#
#.....#
#.....#
#.#...#
##.##.##
#.##.##.##
#.#.##.#####
#.#.########
############
1ドル$번 쿼리가 끝난 직후, 다음과 같이 4ドル$번째 칸에 세워진 벽의 높이가 1ドル$에서 2ドル$가 되어 28ドル$만큼의 물이 차있게 된다.
#
#.....#
#.....#
#.....#
#.#...#
##.##.##
#.##.##.##
#.#.##.#####
#.##########
############
2ドル$번 쿼리가 끝난 직후, 다음과 같이 1ドル$번째 칸에 세워진 벽의 높이가 10ドル$이 되어 58ドル$만큼의 물이 차있게 된다.
#..........#
#....#.....#
#....#.....#
#....#.....#
#....#.#...#
#...##.##.##
#.#.##.##.##
#.#.##.#####
#.##########
############
3ドル$번 쿼리가 끝난 직후, 다음과 같이 3ドル$번째 칸에 세워진 벽의 높이가 9ドル$가 되어 53ドル$만큼의 물이 차있게 된다.
#..........#
#.#..#.....#
#.#..#.....#
#.#..#.....#
#.#..#.#...#
#.#.##.##.##
#.#.##.##.##
#.#.##.#####
#.##########
############