This problem is taken from the 2021 International Olympiad of Informatics:
Problem
Aunty Khong is preparing n boxes of candies for students from a nearby school. The boxes are
numbered from 0 to n − 1 and are initially empty. Box
i\ (0 ≤ i ≤ n − 1) has a capacity of c[i]
candies.
Aunty Khong spends q days preparing the boxes. On day j\ ( 0 ≤ j ≤ q − 1), she performs an
action specified by three integers l[j], r[j] and v[j] where 0 ≤ l[j] ≤ r[j] ≤ n − 1 and
v[j] ≠ 0. For each box k satisfying l[j] ≤ k ≤ r[j]:
If v[j] > 0, Aunty Khong adds candies to box k, one by one, until she has added exactly v[j]
candies or the box becomes full. In other words, if the box had p candies before the action, it
will have min(c[k], p + v[j]) candies after the action.
If v[j] < 0, Aunty Khong removes candies from box k, one by one, until she has removed
exactly −v[j] candies or the box becomes empty. In other words, if the box had p candies
before the action, it will have max(0, p + v[j]) candies after the action.
Your task is to determine the number of candies in each box after the q days.
Example
Consider
c = [10, 15, 13]
l = [0, 0]
r = [2, 1]
v = [20, -11]
This means that box 0 has a capacity of 10 candies, box 1 has a capacity of 15 candies, and box 2
has a capacity of 13 candies.
At the end of day 0, box 0 has min(c[0], 0 + v[0]) = 10 candies, box 1 has
min(c[1], 0 + v[0]) = 15 candies and box 2 has min(c[2], 0 + v[0]) = 13 candies.
At the end of day 1, box 0 has max(0, 10 + v[1]) = 0 candies, box 1 has
max(0, 15 + v[1]) = 4 candies. Since 2 > r[1], there is no change in the number of candies in
box 2. The number of candies at the end of each day are summarized below:
| Day | Box 0 | Box 1 | Box 2 |
|---|---|---|---|
| 0 | 10 | 15 | 13 |
| 1 | 0 | 4 | 13 |
Constraints
1 ≤ n ≤ 200 000
1 ≤ q ≤ 200 000
1 ≤ c[i] ≤ 10\ (for\ all\ 0 ≤ i ≤ n − 1)
0 ≤ l[j] ≤ r[j] ≤ n − 1\ (for\ all\ 0 ≤ j ≤ q − 1)
−10 ≤ v[j] ≤ 10 , v[j] ≠ 0\ (for\ all\ 0 ≤ j ≤ q − 1)
Initial Approaches
Naive Approach
For each query, update each container - this is too slow.
Online Queries
Use a data structure with O(\log(n)) complexity to update your data structure for each query.
Offline Queries
Transform the queries into a more useful form than a list.
For each i\ (0 ≤ i ≤ n − 1), calculate the value of c[i] after q queries.
Further Ideas
Consider that we have one container of capacity c. Store all the queries as they happen in two prefix sums. In the first one, a[0] = 0, a[i+1] = min(a[i]+v[i],0) and in the second, b[0] = 0, b[i+1] = max(b[i]+v[i],0). This means we will be able to discard a[i] and b[i]\ (0 ≤ j ≤ i), b[i] = 0 or a[i] = 0.
We can also discard a[i] and b[i]\ (0 ≤ j ≤ i), b[i] ≤ -c or a[i] \ge c, which means that we just look at the final part of the array, which is already a prefix sum.
Issues
- I don’t know how to implement the above code for multiple values of c.
- I don’t know how to answer queries in \log(q) or \log(n) time
Any help would be greatly appreciated. 