P5338 [TJOI2019] Mr. Toluene’s Rolling Leaderboard.

Mr. Toluene is building an Online Judge. He noticed that people participating in contests care a lot about their rank (obviously). In an ACM-style contest, if the numbers of solved problems are different, the person who solved more problems ranks higher. If the numbers of solved problems are the same, the person with less penalty time ranks higher. Mr. Toluene wants everyone to help design a program: after each time someone gets an accepted solution, tell him how many people are ranked ahead of that person. (This does not include contestants who have exactly the same number of solved problems and the same penalty time.)

The first line contains an integer $T$, the number of test cases. For each test case, input three integers $m, n, \text{seed}$. $m$ is the total number of contestants (numbered $1 \sim m$), $n$ means there are $n$ AC events in total (assume AC events are already deduplicated, i.e., there is no submission of the same problem by the same person). $\text{seed}$ is the seed used to generate the data. Then you must use the following function to generate the data: ```cpp typedef unsigned int ui ; ui randNum( ui& seed , ui last , const ui m){ seed = seed * 17 + last ; return seed % m + 1; } ``` ($\texttt{last}$ is the previous output value. When there has been no output yet, $\texttt{last} = 7$. For multiple test cases, $\texttt{last}$ does not need to be reset.) Each time, generate two values $\texttt{Ria}, \texttt{Rib}$, meaning that contestant $\texttt{Ria}$ gets an AC for one problem, and the added penalty time is $\texttt{Rib}$. (That is, the solved count of $\texttt{Ria}$ becomes $+1$, and the penalty time becomes $+\texttt{Rib}$.) Generate a total of $n$ pairs of data, meaning there are $n$ submissions in total. For all testdata, it is guaranteed that the total sum of penalty times does not exceed $1.5\times 10^6$.

For each submission, output one line with an integer: after contestant $\texttt{Ria}$ gets an AC, how many contestants have a better result than $\texttt{Ria}$.

| Test Point # | 1, 2 | 3, 4 | 5 | 6, 7, 8 | 9, 10 | | :-: | :-: | :-: | :-: | :-: | :-: | | $T$ | $\le10$ | $\le5$ | $\le15$ | $\le5$ | $\le5$ | | $m$ | $\le1000$ | $\le10000$ | $\le10^5$ | $\le10^4$ | $\le10^5$ | | $n$ | $\le1000$ | $\le10000$ | $\le10^5$ | $\le10^6$ | $\le10^6$ | Translated by ChatGPT 5