The problem asks to place $$$n$$$ fishies into a $$$15\times25$$$ tank (including the borders). One way that we can accomplish this is by placing a single fishy at the beginning of rows $$$2$$$ to $$$n+1$$$, and no fishies in rows $$$n+2$$$ to $$$14$$$. This works since at most $$$10$$$ rows will have fishies (one for each fishy) and we have $$$13$$$ rows to work with. Make sure to print the border of the tank properly.

Fun fact, the judge solution places the fishies uniformly at random into the tank. You can view this solution here. (It is definitely not the simplest solution, but the output looks really nice)

We can use a range query data structure to solve this problem. We are interested in two values: the sum of all previous numbers that are less than $$$c_i$$$, and the count of all previous numbers that are less than $$$c_i$$$. With these two values, we may add $$$c_i \cdot cnt$$$ and $$$sum$$$ to get the sum of all previous values lesser than $$$c_i$$$, plus $$$c_i$$$. To get $$$cnt$$$ and $$$sum$$$, we can use two Segment Trees or Fenwick Trees that lets us query the count and sum of cards less than $$$c_i$$$. For the count tree, query the sum from index 1 to $$$i$$$, then update index $$$c_i$$$ to value 1 after processing the card. For the sum tree, query the sum from index 1 to $$$i$$$, then update index $$$c_i$$$ to value $$$c_i$$$ after processing the card. In total, we will make $$$n$$$ queries with each being $$$\log n$$$ complexity, letting us solve this problem in $$$O(N \log N)$$$.

Given a substring $$$p$$$ of $$$s$$$, we want to find the size of the union of the indices contained in substrings of $$$s$$$ that equal $$$p$$$. Intuitively we can picture the matching substrings as intervals of equal length, and we want to know how many indices are covered by the intervals.

To categorizes the substrings of $$$s$$$ by their matches, I used a suffix automaton, but a suffix array can be used with the exact same result (they both serve the same purpose here), so I will refer to the suffix automaton version. The suffix automaton has $$$O(n)$$$ nodes, and each node represents both a set of ending indices, combined with a range of lengths for which substrings ending at all such ending positions are matching. Suppose we want to only look at one node, and suppose we can afford to iterate over all of the endpoints that the node contains. Also suppose that the query string lies inside this node of the automaton. Then, if the length of the query string is $$$x$$$, we can divide the answer to the query into a sum of contributions from each endpoint in this node. Moreover, for an endpoint $$$i$$$, let $$$j$$$ be the largest endpoint in the node that is less than $$$i$$$ (or $$$-1$$$ if $$$i$$$ is the smallest endpoint). Then, the contribution of endpoint $$$i$$$ will be $$$\min(x, i - j)$$$. This is a piecewise linear function, and if we add up the individual functions for each endpoint, we obtain a function for the answer (for queries that refer to substring in this node).

We now want to find an efficient way to store this function, if we want any hope of being able to extend the idea to all nodes in the automaton. My first approach (which passes but is quite slow) uses a sparse segment tree equipped with the operations defined in this problem. The range sum is overkill since we only need a point sum to answer a query, so I implemented the segment tree such that it isn't lazy in order to reduce the overhead. This gives us the ability to add and subtract individual functions to the entire function in $$$O(\log n)$$$ time, as well as to answer queries in $$$O(\log n)$$$ time.

Now we need to find a way to extend this idea to all nodes in the automaton. The suffix link tree is the tree formed by suffix links in the suffix automaton, where the suffix link of a node is a pointer to its parent node. We also know that each endpoint appears exactly in the nodes on some path from the root to the node created upon processing the endpoint during the suffix automaton creation. So, we can build the function for lower nodes in the tree, and then obtain the function for higher nodes with small-to-large merging. When merging one function into the other, we need to consider how the individual functions change as a result of inserting new endpoints. Specifically, if we add an endpoint $$$i$$$, then we want to look for the largest endpoint in the set that is less than $$$i$$$ and the smallest endpoint in the set that is greater than $$$i$$$. Let these be $$$l$$$ and $$$r$$$ respectively, either of which may not exist. If both $$$l$$$ and $$$r$$$ exist, then we want to subtract the function $$$\min(x, r - l)$$$. Then, if $$$r$$$ exists we will add the function $$$\min(x, r - i)$$$. Likewise, if $$$l$$$ exists we will add the function $$$\min(x, i - l)$$$. This gives us a way to merge the segment trees efficiently, and since merging adds an additional $$$O(\log n)$$$ factor to the entire tree traversal, we obtain a complexity of $$$O(n \log^2n)$$$ for maintaining the functions across all nodes in the automaton.

That was the hardest part. All we have left is to determine which queries belong to which node. Since the solution already has a complexity of $$$O(n \log^2n)$$$, I just maintained priority queues in each node and did independent small-to-large merging on them. This also has complexity $$$O(n \log^2 n)$$$, but other methods such as binary lifting can be used to achieve $$$O(n \log n)$$$ complexity for this part. In total the solution has complexity $$$O(n \log^2 n)$$$.

You can see my solution using this approach here.

Merging sparse segment tree is quite overkill still for what we need to accomplish, since we can recognize that the queries will be strictly decreasing (due to the strictly decreasing size property of the suffix automaton nodes as we traverse upwards). Thus, we can sort of use slope trick, where we maintain the slope-changing points of the piecewise linear function in an ordered set, and to process a query we remove the largest slope-changing points until we reach the query size.

You can see my improved solution using this idea here.

The problem involves selecting a subset of building expansion proposals along Austin's East–West highway such that no two approved proposals are closer than a given distance $$$d$$$. Each proposal is located at a distinct integer coordinate $$$x_i$$$ and has an associated profit $$$p_i$$$. The objective is to maximize the total profit while adhering to the spacing constraint, ensuring that if a proposal at $$$x_i$$$ is chosen, no other proposal within a distance $$$d$$$ from $$$x_i$$$ can be selected.

It is natural here to think about this as a dynamic programming problem with the help of a pointer to keep track of the distance requirements. Sorting is crucial because it allows the use of a two-pointer method to quickly find the last proposal that does not conflict with the current one based on the minimum distance $$$D$$$.

$$$\texttt{dp}[i]$$$ is maintained, where $$$\texttt{dp}[i]$$$ represents the maximum profit achievable considering proposals up to the $$$i$$$-th proposal (in sorted order). As the main loop iterates through each proposal $$$i$$$, a secondary pointer $$$j$$$ is used to advance through proposals that are far enough from $$$i$$$ (i.e., where the distance condition $$$\text{points}[i].\text{first} - \text{points}[j].\text{first} \ge D$$$ holds). The variable $$$\texttt{mx}$$$ keeps track of the maximum profit among these valid proposals. Consequently, the state transition is simply:

with $$$p_i$$$ being the profit of the $$$i$$$-th proposal. The overall answer is the maximum value found in the DP array.