diagon_alley's blog

HourRank 31: Problem Basketball tournament [Help Needed]
By diagon_alley, history, 6 years ago, In English

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!

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply