I've participated in JOI 2017 and I'm trying to find the solutions in English. Why don't we create a tutorial with brief explainings of the solutions? I'll contribute by posting the two problems I have solved during the contest, but I'll update when people comment solutions.
If someone speaks Japanese, the official JOI website has posted solutions, but they're only available in Japanese, so you could translate a brief explanation to us :)
Keep an array of differences between consecutive heights, so that delta[i]=A[i]-A[i-1]. Keep the sum of the values of positive differences in a variable pos, and the sum of the absolute values of negative differences in a variable neg. Each time you update a range (l,r), adding X to it, you just need to update differences l and r+1. To update difference i, you reduce its absolute value from pos or neg, depending on its signal, add X to it and adds its absolute value to pos or neg. After each query, the answer will be neg*T-pos*S. Don't forget to use long long.
You have to create K-M stops for the semiexpress line (besides the M fixed ones). For each range between two consecutive express stops, analyze the advantage of creating a semiexpress stop on each station of the range. You can easily calculate what are the stations in that range that one can achieve within time T using only the express and local trains. Call it i. Check how many new stations one could achieve if the semiexpress train stopped at station i+1. Call it Q. Then, keep this value on a heap. After it, check the new number of stations you could achieve if, after it, you created a new stop at station i+1+Q and add to the heap again. Update the values of i and Q and repeat it at most K-M times (because it's the number of stops you can create), or until the value of i exceed the limits of the range you're analyzing.
After this, your answer will be all the stations one can reach with express and local trains plus the K-M greatest values of the heap.
Waiting for comments
Waiting for comments
Waiting for comments
