I don't know how to do the last subtask, anyone have idea ?
# | User | Rating |
---|---|---|
1 | tourist | 3757 |
2 | jiangly | 3647 |
3 | Benq | 3581 |
4 | orzdevinwang | 3570 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | Radewoosh | 3509 |
8 | ecnerwala | 3486 |
9 | jqdai0815 | 3474 |
10 | gyh20 | 3447 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 171 |
2 | awoo | 165 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
5 | maroonrk | 155 |
6 | nor | 154 |
7 | -is-this-fft- | 152 |
8 | Petr | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
I don't know how to do the last subtask, anyone have idea ?
Name |
---|
Also interested
I think it's a good idea to put the problem link.
Here :https://oj.uz/problem/view/JOI19_timeleap
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.
Can you tell me that 2 cases ?
For a segment tree node covering segment $$$[l, r]$$$ you only consider $$$t=L_l$$$ and $$$t=R_l$$$
Can you explain more, please. I don't understand your idea.
Auto comment: topic has been updated by that_bai_xa_hoi (previous revision, new revision, compare).