At the beginning, let us denote by ~I~ the number of input lines starting with letter I (i.e. reconfigurations). Similarly, let ~Q~ be the number of rides.

Simple solutions

One possible simple, although not optimal, solution is to represent the trail as a vector ~A~, where ~A[i]~ denotes the elevation after the ~i^\text{th}~ rail. The complexity of processing a reconfiguration (we call this operation insertion) is ~\mathcal O(n)~. Single query about a ride also takes ~\mathcal O(n)~, so the total time complexity is ~\mathcal O((I+Q)n)~. Moreover, memory complexity is ~\mathcal O(n)~ which is far too high to not exceed the memory limit in large test cases.

Another simple approach is to represent the track as a sorted list of disjoint intervals such that throughout each interval, the difference of elevation over every rail is the same. This way we have insertion and query complexity of ~\mathcal O(I)~, so the entire solution is ~\mathcal O((I+Q)I)~. Memory complexity is ~\mathcal O(I)~.

Model solution

A data structure used in the model solution is a binary tree. Each of its nodes describes an interval (i.e. a number of consecutive rails) ~J = \left[2^k t, 2^k (t+1)\right)~, for some integers ~k~ and ~t~. The information contained in the node is

• ~S_J = \sum_{i \in J} d_i~
• ~H_J = \max\left(\{0\} \cup \left\{\sum_{2^k t \le i \le j} d_i : j \in J\right\}\right)~

The node is a leaf if all the values ~d_i~ are equal. In this case computing ~S_J~ and ~H_J~ is trivial. Otherwise, the node has two sons, with assigned intervals ~J_1 = \left[2^{k-1} (2t), 2^{k-1} (2t+1)\right)~ and ~J_2 = \left[2^{k-1} (2t+1), 2^{k-1} (2t+2)\right)~. In this case ~S_J~ and ~H_J~ are computed as ~S_J = S_{J_1}+S_{J_2}~ and ~H_J = \max\{H_{J_1}, S_{J_1}+H_{J_2}\}~. The root of the tree represents the interval ~\left[0, 2^{\lceil \log_2 n \rceil}\right)~.

The key operation is reconfiguration of the track. It requires inserting or modifying at most ~2 \lceil \log_2 n \rceil~ nodes into the tree. Similarly, processing a query about a ride requires traversing at most ~\lceil \log_2 n \rceil~ nodes. Therefore, such a solution has time complexity of ~\mathcal O((I+Q) \log n)~ and memory complexity ~\mathcal O(I \log n)~.

Even better solution

We are not required to process the input line by line. Instead, we can read in the entire input and know in advance, which parts of the track will be reconfigured at all. Let ~M~ be a sorted vector of the ends of all the intervals contained in all the I-records of the input. We can also assume, that the length of ~M~ is some power of ~2~ (if not, we extend ~M~ by adding some large values).

Now we use a tree very similar to the one described in the previous section. The difference is, that each node describes an interval ~I = \left[M[2^k t], M[2^k (t+1)]\right)~. We can store such a tree in a single vector, just like in the standard implementation of a heap. Since the size of ~M~ is ~\mathcal O(I)~, so the total time complexity is ~\mathcal O((I+Q) \log I)~ and memory complexity is reduced to ~\mathcal O(I+Q)~.