Miraclehehe's blog

[SOLVED] How to do JOI19_TIMELEAP
By Miraclehehe, 14 months ago, In English

I don't know how to do the last subtask, anyone have idea ?

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Also interested

→ Reply
»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I think it's a good idea to put the problem link.

→ Reply
»
14 months ago, # |
  Vote: I like it +4 Vote: I do not like it

WLOG assume that $$$A_j < B_j$$$. Cost of walking is annoying so we can get rid of it by setting $$$[L_i, R_i]$$$ to $$$[L_i-i, R_i-i-1]$$$.

Now at each point we can either increase time or decrease it by paying $$$1$$$. Brute force solution would be trivial: don't change time for as long as possible.

Create a segment tree which will be able to answer the following query: Given a starting time $$$t$$$, find ending time and total cost to walk on a segment $$$[l, r]$$$.

We can get our answer for any $$$t$$$ by setting $$$t=L_l$$$ or $$$t=R_l$$$ depending on the direction our first move in time would be when starting at $$$t$$$.

All we need is a segment tree that for each node stores answer for the $$$2$$$ starting cases.

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

    Can you tell me that 2 cases ?

    → Reply
    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      For a segment tree node covering segment $$$[l, r]$$$ you only consider $$$t=L_l$$$ and $$$t=R_l$$$

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

        Can you explain more, please. I don't understand your idea.

        → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Miraclehehe (previous revision, new revision, compare).

→ Reply