dp[L][R] = cost to join stations of interval [L, R] at point (x[L], y[R]).
Calculate it as min value dp[L][K] + dp[K+1][R] + (x[K+1] - x[L]) + (y[K] - y[R]).
Answer is dp[0][n-1] + path from (x[0], y[n - 1]) to (0, 0)

You need to find the number of primes (let P be a prime) 2 <= P <= 10^7 such that N is the smallest number so Q ^ N % P = 1
From Fermat's little theorem, Q^(P - 1) % P = 1, since P is prime, so N < P.
Also, since Q ^ N % P = 1 Q ^ (2 * N) % P = 1 and Q ^ (P - 1) % P = 1 we know that N is a divisor of P — 1

If N is not the smallest number so Q^N % P = 1, there must be a number D, so D is a divisor of N (like N is a divisor of P — 1)
For each divisor of N, D, check if Q ^ D % P = 1, if that's true, N is not the first number that respects the property.
If N is ok and all divisors fail, P is part of the solution for N

I think you can solve 6 with cascading on segment tree. You also must keep a strange thing in each node. For the lazy part, on each node it will amortize at the end at O(number of els on that node)
the lazy part is like: "Ok, so on this node every value bigger than X will become X". When doing updates on first array, some values may become less than X. You will keep how many values are bigger than X and the product of elements lower than X.
The way I implement lazy is like this: If you pass throw a node, you propagate the lazy to the children and the current node has no lazy. Here, every node will have a X value, and when propagating the lazy, the value X will only increase, so the overall complexity will be O(sizeofnode)

The lazy part comes from how you compute an array c[i] = max(initial_swag, b[1] .. b[i — 1])

I didn't implement this, but it seems good. O(NlogN) time and memory.

Don't know if this will help, but it's the last line of the input. It's the only place where i saw this information
"It is guaranteed that with each change the older parameter value is strictly smaller than the new value."

This is the indended solution: check each regex of length < 16 against all strings.

However, your success largely depends on how many candidate regexes you have (there are various ways to prune regexes), and how you check a string against a regex (again, a lot of options here).

Lets make a list c so that c[i]=a[i]-d[i].

for any [l,r], you need to make (r-l+1)/3 players with the lowest c forwards, (r-l+1)/3 with the highest c defenders, and other (r-l+1)/3 midfielders.

It can be easily done with persistent segment tree in O(q*logn*logn).

There is also a solution, although implementing it during the contest was probably not the best idea.

Define value of player to be difference of his attack and defense. Now sort players by value (and by index in case of ties). From this point build a segment tree on them, and in each node of the tree store all its players sorted by index, and prefix sums of their values alongside.

Now you can perform queries like "how many players with indices in [L..R) have values in [Vmin..Vmax)" in time using standard segment tree operation (you have to run binary search by L and R in each node of the tree). So you can use another bin.search to find values V1 and V2, such that the number of players with indices [L..R) is equal for the value ranges [Vmin..V1), [V1..V2), [V2..Vmax). You can use prefix sums to find sum of values in each of the value ranges, so this gives per query solution.

Now recall that in a standard RSQ segment tree we can do operation like "which maximal prefix of array has sum less than X" in time, which is better that doing binary search by position and calculating sum on prefix inside (which is ). Now apply this idea to the segment tree above, and you don't need the outer binary search by value. So the solution becomes per query.

Finally, you can use fractional cascading to avoid running binary search by L and R in each node, so that you need only one binary search at the root node. This gives per query solution.

I haven't solve (fail on TC #2) and tried another approach: go forward if answer was "c", otherwise go random to L or R, until you stay in a cell from which you can get only "f" answer for all 4 directions. This means that you stay in correct cell, or in cell which is in mirror side of the cube. Then you go 1 circle around cube with two stops at c/f boundary, and dig depending on lengths of last "f" and "c" sequences.

Binary search over answer. Let's check the distance d, i.e. check if n segments is enough. It should be obvious that the greedy strategy should work, i.e. each segment should be as long as possible. Easy to see, that the best way to approximate some interval [x0, x1] is a line that passes through the points (x0, f(x0) + d), (x1, f(x1) + d ), let's say it's a line y = kx + b, then the maximum distance to f(x) will be at point with x = c / k or at the ends of the segment. So we can use one more binary search to find the maximum length of each segment, and build them one by one.

per each test.

There is a solution of O(1).