Subtasks 1 and 2: try to connect every pair of stations on the main line and then find the diameter by checking every pair of stations. In Subtask 2 you have to precompute the stations coordinates along the main line ~x_i = \sum_{j=0}^{i-1} l_j~. These values will be used in all solutions for the other subtasks.

Subtasks 3 and 4: we can try to connect every pair of stations on the main line and then find the resulting diameter. To find the diameter, we can write down the resulting cycle and then iterate through it, keeping a pointer to the opposite position on the cycle (opposite in terms of distance). We also can maintain two queues for each of the halves, keeping the furthest stations in terms of cycle distance plus secondary line length. This will help us to compute the diameter in ~\mathcal O(n)~ time, making the solution run in ~\mathcal O(n^3)~ time in total. In subtask 3, we can use some data structures instead of queues, making the solution run in ~\mathcal O(n^3 \log n)~. However, both solutions are technically complex.

Subtask 5: This subtask requires some clever ideas. First, we can do binary search on the answer. Then, we have to somehow check if it's possible to make the diameter less or equal to some fixed value ~k~. Let's write some inequations.

Let's allow the express line to start and end not only on the stations, but also on arbitrary points ~y~ and ~z~ on the main line. We use the same coordinate system that was used to compute ~x_i~.

If we take a look at some pair ~i~ and ~j~, we can see that if ~d_i+d_j+|x_i-x_j| \le k~ then all pairs of ~y~ and ~z~ work. Otherwise, only ~y~ and ~z~ such that ~d_i+d_j+|x_i-y|+|x_j-z| \le k~ are valid. This formula actually describes a square rotated ~45^\circ~. What we need to do is to try all pairs of ~i~ and ~j~, cross corresponding squares and then check if there is some point where ~y = x_a~ and ~z = x_b~ inside the resulting area.

So far we can just check for such a point by trying all possible pairs of ~a~ and ~b~. However, there is a nice way to perform this check in linear time and not care about its impact on the overall complexity in future. Proceed with a sweep line and keep two pointers: on the lowest point above the square and highest point below the square. Since functions of both positions from the ~x~-coordinate of the sweep line are unimodal, the overall complexity will be ~\mathcal O(n)~.

The total complexity of such a solution is ~\mathcal O(n^2 \log M)~ where ~M~ is the maximal possible answer.

Subtask 6: Now, two more observations are needed. Let's fix ~j > i~ and ~y < z~. Now the pair produces some square iff ~x_j-x_i+d_j+d_i > k~. Let's fix ~j~ and find the intersection of the squares for all possible ~i~. The bounds of the square produced can be rewritten as follows:

$$\displaystyle \begin{cases} z+y \le k+(x_j-d_j)+(x_i-di) \\ z+y \ge (x_j+d_j)+(x_i+d_i)-k \\ z-y \le k+(x_j-d_j)-(x_i+d_i) \\ z-y \ge (x_j+d_j)-(x_i-d_i)-k \end{cases}$$

We can see that the bounds only depend on ~x_i-d_i~ and ~x_i+d_i~. We need only maximal and minimal values of ~x_i-d_i~ and ~x_i+d_i~, so we can use some data structure, for example, segment tree, to find them in ~\mathcal O(n \log n)~ time. The total complexity of this solution is ~\mathcal O(n \log n \log M)~.

Subtasks 7 and 8: Notice that ~x_j-x_i+d_j+d_i > k~ is equal to ~(x_j+d_j)-(x_i-d_i) > k~. It follows that if we iterate through ~j~ in the order of increasing ~(x_j+d_j)~ then the set of ~i~ that is used to take minimum and maximum values is only expanding, i.e. once some particular ~i~ is in the set, it remains there for all remaining values of ~j~. Thus, we can keep current maximum and minimum values of ~x_i-d_i~ and ~x_i+d_i~ without any data structure with the use of the two pointers technique and two sorted arrays. The total complexity of the full-score solution is ~\mathcal O(n \log M)~. Note, that sorting is done at the very beginning and there is no need to re-sort these two arrays in each iteration of binary search.

Another approach to achieve this time bound that doesn't use sort (and thus solves the decision problem itself in linear time) is to get rid of useless elements. We say that station ~i~ dominates station ~j~ if ~d_i > d_j+|x_i-x_j|~. Now, if one station is dominated by the other we can consider only the dominator as the endpoint of the express line (unless the position being dominated is considered for the other end). The set of positions that are not dominated by any other index can be found in linear time by computing prefix and suffix maximums. Now when we use the same solution as for subtask 6, but we query maximum and minimum values for inequality only when considering "good" positions (not dominated by any other positions). This allows us to achieve the situation that the query bound moves only right and we can process each of them in ~\mathcal O(1)~.