백준 32894 (C++) Flowing Fountain

최초 업로드: 2025-10-19 10:56:35

최근 수정 시간: 2025-10-19 10:56:35

게시자: rlatjwls3333

카테고리: 백준

# [Gold I] Flowing Fountain

[문제 링크](https://www.acmicpc.net/problem/32894)

## 문제 설명

Last week, Bill filled a champagne fountain for the first time. Delighted by the champagne pouring from one glass into another, he decided that he wants to organize an even bigger champagne fountain for the next World Finals. He already ordered $n$ glass bowls with different capacities to stack on top of each other to form a huge glass fountain. However, he is still unsure how to pour the champagne into the fountain. One bottle will not be enough and just pouring from the top might not fill every bowl. Bill wants to try out different ways to fill the fountain, but wasting any champagne would be such a shame.

Figure F.1: Illustration of Sample Input 2. The $i$th image visualizes the $i$th query of type '<code>+</code>'.

This is your time to shine! You are tasked with writing a program that simulates the process of pouring champagne into a given fountain. With this program, Bill can now pretend to pour certain amounts of champagne into different levels. If a bowl in some level is already filled up, then the champagne spills over to the first level below it with larger capacity. If the next larger level is also filled, the champagne spills over even further until eventually seeping into the ground, wasting the good champagne. Additionally, Bill also wants to know at some times during the simulation process how much champagne currently is in a certain level.

## 입력

The input consists of:

<ul>
	<li>One line with two integers $n$ and $q$ ($1\leq n, q \leq 3 \cdot 10^5$), the number of levels and the number of queries.</li>
	<li>One line with $n$ distinct integers $c$ ($1\leq c \leq 10^9$), the capacity of each level in litres. The levels are given in order from top to bottom.</li>
	<li>$q$ lines, each describing a query. The first symbol $t$ ($t \in \{$'<code>+</code>', '<code>?</code>'$\}$) describes the type of the query. The format of the rest of the line depends on $t$:
	<ul>
		<li>$t=$'<code>+</code>': Two integers $\ell$ and $x$ follow ($1 \leq \ell \leq n$, $1 \leq x \leq 10^9$), the level into which Bill wants to pour $x$ litres of champagne.</li>
		<li>$t=$'<code>?</code>': One integer $\ell$ follows ($1 \leq \ell \leq n$), the level for which Bill requests the current amount of champagne in litres.</li>
	</ul>
	</li>
</ul>

It is guaranteed that there is at least one query of type '<code>?</code>'.

## 출력

For each query of type '<code>?</code>', output the amount of champagne in the requested level in litres.

## 풀이
현재의 크기보다 큰 다음 크기의 위치를 찾고, 물을 부을 때는 다 찬 곳은 분리 집합으로 한번에 뛰어넘으면서 해결했습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 300'002;

int parent[MAX], nextBig[MAX], _size[MAX], cur[MAX];

int _find(int x) {
    if(x==parent[x]) return x;
    return parent[x] = _find(parent[x]);
}

void _union(int x, int y) {
    x = _find(x);
    y = _find(y);
    if(x>y) parent[y]=x;
    else parent[x]=y;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int n, q; cin >> n >> q;
 for(int i=1;i<=n;i++) {
 cin >> _size[i];
 parent[i]=i;
 }
 parent[n+1]=n+1;

vector<int> decreasing;
 for(int i=n;i>=1;i--) {
 nextBig[i]=n+1;
 while(!decreasing.empty() && _size[decreasing.back()]<=_size[i]) decreasing.pop_back();
 if(!decreasing.empty()) nextBig[i] = decreasing.back();
 decreasing.push_back(i);
 }

while(q--) {
 char ch; int l; cin >> ch >> l;
 if(ch=='+') {
 int x; cin >> x;
 l = _find(l);
 while(l!=n+1 && x) {
 int cnt = min(x, _size[l]-cur[l]);
 cur[l] += cnt;
 x -= cnt;
 if(cur[l]==_size[l]) {
 _union(l, nextBig[l]);
 l = _find(l);
 }
 }
 } else {
 cout << cur[l] << '\n';
 }
 }
}
```