Distributing Candies (2021 IOI Q1)

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. :grin:

(https://codeforces.com/blog/entry/92083?#comment-807860)
(https://codeforces.com/blog/entry/92083?#comment-808090)
Generally codeforces is better than codechef if you want the solutions of problems in such big competitions.