Hello everyone. I am really stuck at this problem, can you please provide a solution? Problem Link : Overlapping Boxes. Thanks in advance :).

Problem Source : TCS Mockvita 2

Before contest

Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4)

07:16:04

Register now »

Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4)

07:16:04

Register now »

*has extra registration

Before contest

Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4)

07:16:04

Register now »

Codeforces Round #606 (Div. 2, based on Technocup 2020 Elimination Round 4)

07:16:04

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3556 |

2 | wxhtxdy | 3520 |

3 | Radewoosh | 3409 |

4 | Benq | 3368 |

5 | mnbvmar | 3280 |

6 | ecnerwala | 3278 |

7 | LHiC | 3276 |

8 | sunset | 3264 |

9 | maroonrk | 3159 |

10 | TLE | 3145 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 189 |

2 | Radewoosh | 177 |

3 | tourist | 173 |

4 | antontrygubO_o | 172 |

5 | Vovuh | 167 |

6 | PikMike | 166 |

7 | rng_58 | 157 |

8 | majk | 156 |

9 | farmersrice | 153 |

9 | Um_nik | 153 |

Hello everyone. I am really stuck at this problem, can you please provide a solution? Problem Link : Overlapping Boxes. Thanks in advance :).

Problem Source : TCS Mockvita 2

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/14/2019 06:48:56 (e1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Hint sweep line technique

SolutionLet's move across the x-axis from 0 to $$$MAX_X = 1e4$$$ and maintain the values of the $$$x$$$-th coloumn from the grid. We need to recalculate it efficiently using the $$$x-1$$$-th coloumn somehow. If there is no rectangle having $$$x$$$ as a leftmost or rightmost point, its clear that $$$x$$$-th coloumn is equal to the $$$x-1$$$-th one. Otherwise there are two possible types of actions for $$$x$$$:

- $$$x$$$ is the rightmost coordinate of the rectangle

- $$$x$$$ is the leftmost coordinate of the rectange

For each action of the first type we need to decrease values in the appropriate range by the appropriate cost value. And for the second type actions we need to increase the values in the same way. To do in efficiently you can construct a preffix array for that values and then add it to the $$$x-1$$$-th coloumn and that is — you've got an $$$x$$$-th coloumn. Then just update the maximum and its count.

Complexity is $$$O(MAX_X * MAX_Y + N)$$$

Here is my brief implementation https://ideone.com/82XDr3 . There might be some bugs, but anyway it can help you understand the idea.

Thank you so much for helping out with such an elaborate solution :).