Codeforces Round #804 (Div. 2)
5 өдрийн дараа |
D. Усны савнууд
хугацааны хязгаарлалт 2 секунд
санах ойн хязгаарлалт 256 мегабайт
оролт стандарт оролт
гаралт стандарт гаралт
Дээр дээрээсээ давхарлан байрласан $n$ усны саваас тогтох систем зурагт үзүүлснээр оршино. Усны савууд дээрээс доошоо $1$-с $n$ хүртэл дугаарлагдсан бөгөөд $i$-р савны эзэлхүүн $a_i$ гэж үзье.
Анх бүх сав хоосон байсан. $i$-р сав халих үед халисан ус нь ($i+1$) саванд ордог. $n$-р савнаас хальсан ус шалан дээр асгарна.
Таны даалгавар үйлдлийн дарааллыг гүйцэтгэх процессийг загварчлах юм. Энд дараах $2$ төрлийн үйлдэл байна:
- $p_i$-р саванд $x_i$ литр ус нэмэх
- $k_i$-р саванд байгаа усны хэмжээг хэвлэх
Та $2$ төрлийн хүсэлтийг биелүүлэх үед бүх ус урсаж, хальж дууссан байна гэж үзээрэй.
Оролт
Эхний мөрөнд савны тоо $n$ ($1 ≤ n ≤ 2·10^5$) байна. Дараагийн мөрөнд савны эзэлхүүнүүдийг илэрхийлэх $a_1, a_2, ... , a_n$ ($1 ≤ a_i ≤ 10^9$) дараалал өгөгдөнө. Савны эзэлхүүнүүд дээрээс доош ихсэх албагүйг анхаараарай (хоёрдугаар жишээ тестийг хар). Гуравдугаар мөрөнд хүсэлтийн тоо $m$ ($1 ≤ m ≤ 2·10^5$) байна. Дараагийн $m$ мөрөнд хүсэлтийн мэдээлэл байрлана. Эхний төрлийн хүсэлт "$1 p_i x_i$" хэлбэртэй, хоёрдугаар төрлийн хүсэлт "$2 k_i$" хэлбэртэй ($1 ≤ p_i ≤ n$, $1 ≤ x_i ≤ 10^9$, $1 ≤ k_i ≤ n$).
Гаралт
Хоёрдугаар төрлийн хүсэлт бүрт харгалзах саванд байгаа усны хэмжээг хэвлэ.
Орчуулсан: zoloogg
Жишээ тэстүүд
Оролт
2 5 10 6 1 1 4 2 1 1 2 5 1 1 4 2 1 2 2
Гаралт
4 5 8
Оролт
3 5 10 8 6 1 1 12 2 2 1 1 6 1 3 2 2 2 2 3
Гаралт
7 10 5