Editorial for Topium

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.

An impurity at $(x, y)$ ~(x, y)~ will be counted towards the melting point only if the top left corner of the plate is between $(x-R, y-C)$ ~(x-R, y-C)~ and $(x, y)$ ~(x, y)~.

$\text{[math]}$

The plate will only contain the impurity (red) if its top left corner (black) is inside the blue box.

Draw the bounding rectangle of each impurity. Each rectangle has a value equal to the impurity strength. Find the highest possible total value of rectangles covering a point.

$\text{[math]}$

To solve this problem, store the left and right edges of each rectangle and sort them by $x$ ~x~ coordinate. Perform a line sweep across the $x$ ~x~ axis. Store the value of each point on the $y$ ~y~ axis using a segment tree. When a left edge from $y_1$ ~y_1~ to $y_2$ ~y_2~ of a rectangle of value $v$ ~v~, add $v$ ~v~ to the segment tree from $y_1$ ~y_1~ to $y_2$ ~y_2~. When you reach a right edge, subtract $v$ ~v~. Each time you add or subtract an edge, also find the maximum value in the segment tree. The maximum of these maximums will be your answer.

Coordinate compress the $y$ ~y~ values because they can be up to $10^9$ ~10^9~.

Tips:

You cannot cut outside of the gem, all edges of your cut must be between $(1, 1)$ ~(1, 1)~ and $(n, m)$ ~(n, m)~
Some impurities have negative values, so in some cases, it may be the best option to look for a pure fragment
Make sure you include all impurities inside your cut when adding up the values, even the negative ones

Time Complexity: $\mathcal O(K \log M)$ ~\mathcal O(K \log M)~

Comments

There are no comments at the moment.