Milk Buckets
실버 II의견: 0
There are \(N\) (\(1\le N\le 2\cdot 10^5\)) buckets in a stack where the \(i\)-th
bucket from the top has capacity \(a_i\) gallons (\(1\le a_i\le 10^9\)). A tap above
the top bucket sends one gallon of milk per second into the first bucket per
second. There is also a pool below bucket \(N\).
When a bucket reaches its capacity after \(t\) seconds, at the start of the
\(t+1\)th second it flips to dump its contents into either the bucket below if it
is not the last bucket or the pool otherwise (it reverts back to filling at the
end of the \(t+1\)th second). A bucket cannot collect milk while it is flipped;
any milk arriving at the bucket above during this second is lost. Additionally,
any amount of milk exceeding the capacity of the bucket below is lost.
Handle \(Q\) (\(1\le Q\le 3\cdot 10^5\)) queries, each specified by three integers
\(i\), \(v\), and \(t\):
- First, set \(a_i=v\) (\(1\le i\le N, 1\le v \le 10^9\)).
- Then answer the following question: Suppose that at time \(0\), all buckets as well as the pool are empty. Determine the number of gallons of milk in the pool after \(t\) seconds (\(1\le t\le 10^{18}\)).
The \(a_i=v\) updates persist through later queries.
Problem credits: Akshaj Arora
SCORING
- Inputs 4-5: \(N \le 10, Q\le 100\), and all \(t\le 10^4\)
- Inputs 6-11: \(N\le 10^3, Q\le 10^4\)
- Inputs 12-23: No additional constraints.
Problem credits: Akshaj Arora
The first line contains \(N\).
The second line contains \(a_1\dots a_N\).
The next line contains \(Q\).
Then the following \(Q\) lines contain three integers \(i\), \(v\), and \(t\). This
means that you should set \(a_i=v\) and then answer the question for \(t\).
Output the answer to each question on a separate line.
3
1 1 1
30
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 10
1 2 1
1 2 2
1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 2 8
1 2 9
1 2 10
2 2 1
2 2 2
2 2 3
2 2 4
2 2 5
2 2 6
2 2 7
2 2 8
2 2 9
2 2 100
0
0
1
1
2
2
3
3
4
0
0
0
0
1
1
1
2
2
2
0
0
0
0
1
1
1
2
2
2When \(a=[1, 1, 1]\),
- Bucket \(1\) flips at times \(2,4,6,\dots\)
- Bucket \(2\) flips at times \(3,5,7,\dots\)
- Bucket \(3\) flips at times \(4,6,8,\dots\)
When \(a=[2, 1, 1]\),
- Bucket \(1\) flips at times \(3,6,9,\dots\)
- Bucket \(2\) flips at times \(4,7,10,\dots\)
- Bucket \(3\) flips at times \(5,8,11,\dots\)
When \(a=[2, 2, 1]\),
- Bucket \(1\) flips at times \(3,6,9,\dots\)
- Bucket \(2\) flips at times \(4,7,10,\dots\)
- Bucket \(3\) flips at times \(5,8,11,\dots\)
2
1 2
10
1 1 1
1 1 2
1 1 3
1 1 4
1 1 5
1 1 6
1 1 7
1 1 8
1 1 9
1 1 100
0
0
0
2
2
2
2
4
43
1 1 1
1
1 1 1000000000000000000499999999999999999riseoj 작성
출처 올림피아드 > USACO > 2025-2026 > Third Contest > Silver
평가 및 의견
Milk Buckets
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Milk Buckets