Editorial for Boxen in Boxen


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

This problem requires a number of observations to be made. Firstly, it is guaranteed that the optimal order of play will be sorted by slope: \frac d {b-1}. If the slope of an element is greater, it will always be optimal to play it over any element with a lower slope. It is also clear that any element with b=1 can be ignored, since it will never increase our answer.

Unfortunately, this is not enough and will take \mathcal{O}(N^2 \log N). For full points, you need to use a segment tree or similar range query data structure. Assign a position in the tree for each box based on their slope (e.g. the smallest slope=1, then 2nd slope is 2, etc.). The fox will be given position 0. We can think of our answer as the sum of values in our tree. Since each box is multiplied by the b_i values after them, whenever you add a box, you can use lazy propagation to multiply the all the boxen before it by their b_i value. However, some boxen are not yet added when they are multiplied! This can be solved by initializing each leaf node to 1. Initially, don't want to consider all leaf nodes, so a secondary array keeps track of what nodes are "active", the boxen that have already been added. You also multiply the leaf node of the new box by its b_i value. In short, each node keeps a running total of its value, and that value is added to the sum once the box is added.

However, this is still not able to get full points, since you will not always immediately add all the boxen in a query. For each query, keep a list of boxen that have not yet been added. You can evaluate pre[i] for any box by querying the range of numbers before the box. Using this value, we determine if it is optimal to add the box. Unfortunately, one cannot loop through the list. We already know that a box will always be added before another box if its slope is lower. Thus, we can keep a sorted list (such as std::set) of the boxen that have not yet been added. Thus we only have to look at 1 box that will not be added for each query.

Time Complexity: \mathcal{O}(N \log N)


Comments

There are no comments at the moment.