Let's say that we are given some permutation (order in which pizzas are made) ~\pi_i~, and we wish to calculate the tip we'll get:

$$\displaystyle \sum_{i=1}^n \left(R_{\pi_i} - \sum_{j=1}^i V_{\pi_j}\right) = \sum_{i=1}^n R_{\pi_i} - \sum_{i=1}^n (n-i+1) V_{\pi_j}$$

We can now conclude that order with regard to deadlines is not important, and that order with regard to durations must be increasing, so that pizzas that are baked longer are multiplied by a smaller coefficient.

Brute force solution that sorts the pizzas after each update and calculates the above sum has complexity ~\mathcal O(N \log N)~ or ~\mathcal O(N)~ and is worth 50 points.

The constraint given to ~V_i~ was sort of a hint that can lead to a simple solution: in some array ~cnt~ we can use ~cnt[x]~ to store the number of pizzas having baking time ~x~. For ~V_i~ under ~1000~, we calculate every query by traversing the ~cnt~ array. This approach was worth 80 points.

We can use some data structure like segmented array (BIT) for implementing the ~cnt~ array, and additional sequence that keeps the ~V_i~ sums (~sum[x] = cnt[x] \times x~). To remove duration ~V_p~ for some pizza ~p~, we must increase our solution by:

$$\displaystyle V_p \sum_{i=0}^{V_p} cnt[i] + \sum_{i = V_p+1}^{maxV} sum[i]$$

Now we decrease ~cnt[V_p]~ by ~1~ and ~sum[V_p]~ by ~V_p~. In order to insert ~V_p~ into our structure, we do the same thing, but with inversed signs and order (change ~cnt~ and ~sum~ first and then decrease the solution). ~R_i~ sums are trivial to calculate and don't require any data structures.

We can answer each query in ~\mathcal O(\log maxV)~, and total complexity is ~\mathcal O((N+P) \log maxV)~ which is good enough for obtaining maximum points for this task.

There is an alternative solution that doesn't depend on ~maxV~. Idea is to maintain the sorted sequence of all the baking durations, along with the sums and corresponding coefficients. This can be achieved by using a balanced tree (online solution), and by using a segmented array built on top of the sorted sequence of all the durations (offline solution).

The complexity of this approach is ~\mathcal O((N+P) \log(N+P))~.