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) will be counted towards the melting point only if the top left corner of the plate is between (x-R, y-C) and (x, y).

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.

To solve this problem, store the left and right edges of each rectangle and sort them by x coordinate. Perform a line sweep across the x axis. Store the value of each point on the y axis using a segment tree. When a left edge from y_1 to y_2 of a rectangle of value v, add v to the segment tree from y_1 to y_2. When you reach a right edge, subtract 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 values because they can be up to 10^9.


  • You cannot cut outside of the gem, all edges of your cut must be between (1, 1) and (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)


There are no comments at the moment.