For the first subtask, print the maximum score so far for the first problem. This subtask was intended to reward users who read all of the problems.

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

For the second subtask, perform the instructions listed in the problem statement. Keep an array which stores the highest submissions for each problem, sort a copy of this array, and calculate the PP.

Time Complexity: ~\mathcal{O}(N \times P \log P)~

For the third subtask, notice that ~r^{i-1}=1~. Then the user's PP is equal to ~\sum_{i=1}^{100\,000} s_i~. In this formula, sorting is not needed. For each query, find the increase in the total sum, then output the total sum.

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

For the fourth subtask, it is only necessary to get the user's top ~5~ submissions. All of the other submissions are covered by the relative error, since ~r^5 + r^6 + r^7 + \dots < 10^{-7}~. Record the problems which are in the top ~5~, and update this small list when necessary.

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

The fifth subtask is intended to reward submissions which are not fast enough to solve the sixth subtask. Some reasons include:

• using long double instead of double
• calculating the powers of ~r~ every time (instead of using an array)
• runtime is slower than ~\mathcal{O}(N \log N)~

For the sixth subtask, it is important to know about merging two lists of scores. Let ~S~ be the final list, and ~Q+R=S~ where ~Q~ and ~R~ are smaller lists. Suppose all of the elements in ~Q~ are equal/greater than the elements in ~R~, and the PP for ~Q~ and ~R~ are known. Then the PP for ~S~ can be calculated easily by this formula:

$$\displaystyle PP(S) = PP(Q) + r^{\text{size}(Q)} \times PP(R)$$

Then segment trees can be used to quickly update the PP. First, keep an array of all ~(V_i, i)~ pairs, then sort the array by ~V_i~. At the very beginning, the leaves of the segment tree are all set to size ~0~, since there are no submissions yet. For every update, the old leaf needs to be set to size ~0~, and the new leaf set to size ~1~. Every node contains its own PP and size, and the user's PP can be found at the root of the segment tree. Make sure to keep another array which stores ~r^0, r^1, \dots, r^{100\,000}~ so that the formula is efficient. Lazy propagation is not needed.

To do this problem onlinely, it is possible to use a balanced binary search tree (BBST) and the formula described above (except with a slight modification). Every node contains a PP, and lazy propagation is not needed because every node can store its size. I don't see a way to use pb_ds, sorry Kirito.

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