Subtask 1

For the first subtask, we can maintain the final order of the scoreboard by keeping a list of contestants. When a contestant makes a submission, we need to remove that contestant from the list, and insert it at the ~r_i^{th}~ index. Since each contestant submitted to at most one problem, it can be seen that the time of the single submission plus the penalty for that submission must be sorted in ascending order. If we assign each submission a time of ~1, 2, \dots, K~, then this can be achieved by adjusting the penalties for each contestant until their sum of times plus penalty is greater than the contestant who ranked above them.

Time Complexity: ~\mathcal{O}(N \cdot K)~

Subtask 2

For the second subtask, we can see that the invariant that the sum of times plus penalties must always be sorted in ascending order after every change to the scoreboard. If we create a graph where the nodes are the number of problems a contestant solved, we can add a directed edge between nodes to represent an inequality between the sum of times plus penalties. We add edges to the graph after every submission. We can recognize that this graph is acyclic, and thus, has a topological order. If we consider the submissions in topological order, we can assign penalties in a manner similar to subtask 1.

Time Complexity: ~\mathcal{O}(N \cdot K)~

Subtask 3

In subtask 1, rather than using a list of contestants, we can instead use a balanced binary search tree (or square root decomposition) to maintain the rank of the contestants. The balanced binary search tree for this problem does not have a key, and instead allows for insertions at an arbitrary index. It must also support finding the index of an element in the tree, deletions at an index, and optionally, selecting an element at an index (depending on the implementation of the solution). The penalties can be assigned in a similar manner.

Time Complexity: ~\mathcal{O}(N \cdot M + K \cdot \log N)~

Subtask 4

Similar to subtask 3, we can use a balanced binary search tree to maintain the rank of the contestants. We can also use the idea from subtask 2 of building a graph based on the inequalities between the sum of times plus penalties. A key observation is that edges will only need to be added between the nodes representing the contestants immediately before and after the contestant who made the submission. Thus, each submission only creates at most ~2~ new edges. The penalties can then be assigned in the same way.

Time Complexity: ~\mathcal{O}(N \cdot M + K \cdot \log N)~

Alternate approach by Dormi

Rather than creating a graph, we can create separate balanced binary search trees for each number of problems solved. When a submission is made, instead of removing nodes from the balanced binary search tree, we can make their old node a "ghost node", and keep them in the same position, but ignore them when dealing with all operations. A new node is then inserted into the balanced binary search tree corresponding to the updated number of problems solved. The penalties can then be computed individually for each problem based on their order in the balanced binary search tree.