| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 497 | 268 | 243 | 55.734% |
현빈이가 사는 도시에는 날마다 콘서트가 열린다.
현빈이는 소음에 민감해 $N$개의 방음벽을 설치하였다. 방음벽은 순서대로 1ドル$번부터 $N$번까지의 번호를 가지며, $i$번 방음벽은 $D_i$만큼의 소음을 흡수할 수 있다. 방음벽을 설치한 뒤, 현빈이는 앞으로 모든 콘서트는 두 연속한 방음벽 사이에서만 열 수 있도록 규칙을 세웠다. 즉, 앞으로 모든 콘서트가 열리는 위치는 어떤 정수 $c$에 대해 $c$번 방음벽과 $c+1$번 방음벽 사이여야 한다. (1ドル\leq c<N$)
모든 소음을 흡수해 조용한 나날을 보내려던 현빈이의 계획과 달리, 방음벽이 콘서트의 소음을 완전히 감당하지 못하는 일이 생기기도 했다. 예를 들어, $x$의 소음을 가진 콘서트가 $c$와 $c+1$번 방음벽 사이에서 열렸다고 하자. 이때 $c$번 방음벽이 흡수할 수 있는 소음은 $\min(D_c,x)$뿐이고, 만약 흡수되지 못한 소음이 있다면 해당 소음은 $c-1$번 방음벽으로 향하게 된다. 마찬가지로, $c+1$번 방음벽 또한 $\min(D_{c+1},x)$만큼의 소음만 흡수하고, 흡수되지 못한 소음은 $c+2$번 방음벽으로 향하게 된다. 이 과정은 더 이상 흡수될 소음이 없거나 소음을 흡수할 방음벽이 남아 있지 않을 때까지 반복된다.
현빈이는 매 콘서트가 끝난 직후, $N$개의 모든 방음벽에 대하여 각 방음벽이 흡수한 소음의 양만큼 방음벽을 보강할 것이다. 즉, 어떤 방음벽 $k$가 흡수한 소음이 $x$라면, 콘서트가 끝난 직후 $k$번 방음벽이 흡수할 수 있는 소음은 $D_k+x$가 된다.
현빈이는 $Q$회에 걸쳐 아래 작업 중 하나를 진행한다.
2ドル$번 작업을 진행할 때마다 주어진 방음벽이 흡수할 수 있는 소음을 빠르게 계산해 보자.
첫째 줄에 현빈이가 설치한 방음벽의 수 $N$이 주어진다. (2ドル\leq N \leq 200,000円$)
둘째 줄에 $N$개의 방음벽이 흡수할 수 있는 소음의 크기 $D_1, D_2, \cdots, D_N$이 공백으로 구분되어 주어진다. (1ドル\leq D_i \leq 10^9$)
셋째 줄에 현빈이가 진행한 작업의 수 $Q$가 주어진다. (1ドル\leq Q \leq 200,000円$)
이후 $Q$개의 줄에 걸쳐, 현빈이가 진행할 작업에 대한 정보가 지문과 같은 형식으로 주어진다. 2ドル$번 작업이 최소 한 번 이상 주어짐이 보장된다.
입력으로 들어오는 모든 수는 정수이다.
$Q$개의 줄에 현빈이가 진행한 모든 2ドル$번 작업의 결과를 순서대로 출력한다.
6 5 1 2 4 7 3 5 1 2 1 2 3 1 4 7 2 3 2 5
3 6 14
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2025 예선 E번