Head-on solution have complexity O(2^40)=O(10^12). It's very slow. How do it faster?

I used 40=30+20
First 20- memorization
second 20 as 2^20=10000000- that normaly

Could you explain your solution more in detail?
"First 20- memorization" What it mean in Russian?
I understood that what we do with second 20. But can not understood that what we do with first 20. =)

I meant that first 20 also as 2^20 or with brute force aproach,
but result of first 20 we place in arr[1..1000000](memorization)
sort arr than in second 20 use log-bin search in arr.

Thank you very much. You is good man! I got AC. =)

It's a bit more complicated than that because you should care about rod not getting off the rails during the process as well, so you can't just pick arbitrary memorized sequence which gives suitable end-result, it also must stay within limits while it performs memorized shiftings. Looks like segment tree algo, not just plain binary search (or tests are very weak).

P.S: Got AC with 0.5 sec and 44Mb, probably could've done better. For every 2^20 endings I track range of start values where it is suitable (i.e. fits for its entire internal history), then for every 2^20 beginnings (sorted) I track min/max of currently active segments via two heaps.

Edited by author 16.08.2022 11:51

P.P.S: Ah, I'm dumb! Memorizing first 20 leads to much easier algo when last 20 are brute-forced (not vice versa). 0.265 sec, 7 Mb. Yet, coding that monster from previous "P.S" was fun :)