Hey Everyone, Can anyone tell how to solve the large test case for the problem. Editorial seems a way difficult to understand. If anyone solved that problem, pls help me. Thanks!

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

1 | MiFaFaOvO | 3681 |

2 | tourist | 3673 |

3 | Um_nik | 3493 |

4 | apiadu | 3397 |

5 | 300iq | 3317 |

6 | maroonrk | 3250 |

7 | Benq | 3230 |

8 | LHiC | 3229 |

9 | TLE | 3223 |

10 | ecnerwala | 3216 |

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

1 | antontrygubO_o | 192 |

2 | Errichto | 185 |

3 | tourist | 182 |

4 | vovuh | 170 |

5 | pikmike | 168 |

6 | ko_osaga | 165 |

7 | Radewoosh | 164 |

8 | Um_nik | 162 |

9 | 300iq | 155 |

10 | rng_58 | 153 |

Hey Everyone, Can anyone tell how to solve the large test case for the problem. Editorial seems a way difficult to understand. If anyone solved that problem, pls help me. Thanks!

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/09/2020 17:41:11 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

We will do parallel binary search (if you don't know what this is, you can try finding the blog in codeforces) on the answer K. Now we have update events (value X appears on position i) and query even (what's the maximum value of sum * length of a subinterval between L, R). Both queries can be done in with segment tree. Unfortunately this way the complexity is and will pass for 58 points. But if we use the fast segment tree from Al.Cash's blog it will pass. Furthermore as all values are nonnegative we can actually replace the segment tree with dsu.

For the segment tree you will need the following in each node:

1) Available suffix length and sum.

2) Available prefix length and sum.

3) Answer and length of the whole interval.

This way we can merge the nodes in time.

Ohh Thanks! I am starting to get some intuition for that. Pls share ur code too for more clearity.