| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 73 | 26 | 22 | 41.509% |
일렬로 $N$개의 칸이 이어진 땅이 있다. 각 칸의 높이는 $h_1, h_2,\cdots, h_N$ 이다.
비가 충분히 많이 내려 현재 땅 위에 물이 최대한으로 고여 있다. 물은 좌우 양쪽이 자신보다 높은 지형으로 둘러싸인 구간에만 고인다. 구체적으로 $i$번 칸에 높이 $x$까지 물이 차오르기 위해선 $l < i < r$이면서 $h_i < x \le \min(h_l, h_r)$을 만족하는 $(l, r)$이 존재해야 한다.
연우는 이 땅에 배수구를 설치하여 물을 빼내려고 한다. 어떤 칸 $i$에 배수구를 설치하면, 그 칸의 높이는 0ドル$이 되고 해당 칸을 통해 연결된 물은 전부 빠져나가게 된다.
연우는 총 $Q$개의 배수구를 차례대로 설치한다. 이전에 설치된 배수구는 유지된다. 배수구를 설치하기 전의 물의 총량과, 각 쿼리마다 배수구를 하나 설치한 이후 땅 위에 남아 있는 물의 총량을 구하여라.
첫째 줄에 정수 $N$이 주어진다. (1ドル \le N \le 200,000円$)
둘째 줄에 $N$개의 정수 $h_1, h_2, …, h_N$이 주어진다. (1ドル \le h_i \le 10^9$)
셋째 줄에 정수 $Q$가 주어진다. (1ドル \le Q \le N$)
넷째 줄부터 $Q$개의 줄에 걸쳐, 각 줄에 정수 $i$가 주어진다. (1ドル \le i \le N$)
입력으로 주어지는 모든 $i$는 서로 다르다.
첫째 줄에, 배수구를 설치하기 전 땅에 고인 물의 총량을 출력한다.
다음 $Q$개의 줄에 걸쳐, 각 쿼리마다 배수구를 설치한 이후에 남아 있는 물의 총량을 한 줄에 하나씩 출력한다.
7 5 2 6 1 3 2 4 2 4 2
9 4 1
배수로를 설치하기 전의 물의 총량은 0ドル+3+0+3+1+2+0=9$이다.
4ドル$번 칸에 배수구를 설치한 이후 땅 위에 남아 있는 물의 총량은 0ドル+3+0+0+0+1+0=4$이다.
2ドル$번 칸에 배수구를 설치한 이후 땅 위에 남아 있는 물의 총량은 0ドル+0+0+0+0+1+0=1$이다.
10 5 2 4 1 3 1 6 2 3 2 3 4 8 2
15 5 4 2