P3960 [NOIP 2017 Senior] Lineup

NOIP 2017 D2T3.

Sylvia is a girl who loves studying. Some time ago, Sylvia took part in the school’s military training. As is well known, during training they must stand in a square formation. There are $n \times m$ students in Sylvia’s formation, with $n$ rows and $m$ columns. For convenience, at the beginning of training, the instructor numbers the students from $1$ to $n \times m$ in order from front to back and from left to right (see the example below). That is: initially, the student at row $i$, column $j$ has ID $(i-1)\times m + j$. However, during the formation drills, students often need to leave the formation for various reasons. In one day, there are $q$ such leave events. Each leave event is described by a pair $(x, y)$ ($1 \le x \le n, 1 \le y \le m$), meaning the student at row $x$, column $y$ leaves. After a student leaves, an empty spot appears. To keep the formation tidy, the instructor issues the following two commands in order: 1. Align left. The first column remains still, and all students shift left to fill the gap. It is easy to see that after this command, the empty spot is at row $x$, column $m$. 2. Align forward. The first row remains still, and all students shift forward to fill the gap. It is easy to see that after this command, the empty spot is at row $n$, column $m$. The instructor stipulates that no two or more students may leave at the same time. That is, after the previously departed student has returned, the next student may leave. Therefore, when each departed student is to return, there is exactly one empty spot at row $n$, column $m$, and the student naturally fills that position. Because standing in formation is really boring, Sylvia wants to compute, for each leave event, the ID number of the student who leaves. Note: A student’s ID never changes due to leave events, though the order of IDs in the formation may become scrambled after events.

The input consists of $q+1$ lines. The first line contains $3$ positive integers $n$, $m$, and $q$, separated by spaces, indicating a formation of $n$ rows and $m$ columns, with a total of $q$ events. The next $q$ lines describe the $q$ events in the order they occur. Each line contains two integers $x, y$, separated by a space, indicating that in this leave event, the student currently at row $x$, column $y$ leaves.

For each event, in the input order, output one line with a single integer: the ID of the student who leaves in that event.

【Explanation for Sample Input/Output $1$】 $$\begin{matrix} \begin{bmatrix} 1 & 2 \\ 3 & 4 \\ \end{bmatrix} & \Rightarrow & \begin{bmatrix} & 2 \\ 3 & 4 \\ \end{bmatrix} & \Rightarrow & \begin{bmatrix} 2 & \\ 3 & 4 \\ \end{bmatrix} & \Rightarrow & \begin{bmatrix} 2 & 4 \\ 3 & \\ \end{bmatrix} & \Rightarrow & \begin{bmatrix} 2 & 4 \\ 3 & 1 \\ \end{bmatrix} \\[1em] \begin{bmatrix} 2 & 4 \\ 3 & 1 \\ \end{bmatrix} & \Rightarrow & \begin{bmatrix} 2 & 4 \\ 3 & \\ \end{bmatrix} & \Rightarrow & \begin{bmatrix} 2 & 4 \\ 3 & \\ \end{bmatrix} & \Rightarrow & \begin{bmatrix} 2 & 4 \\ 3 & \\ \end{bmatrix} & \Rightarrow & \begin{bmatrix} 2 & 4 \\ 3 & 1 \\ \end{bmatrix}\\[1em] \begin{bmatrix} 2 & 4 \\ 3 & 1 \\ \end{bmatrix} & \Rightarrow & \begin{bmatrix} 2 & \\ 3 & 1 \\ \end{bmatrix} & \Rightarrow & \begin{bmatrix} 2 & \\ 3 & 1 \\ \end{bmatrix} & \Rightarrow & \begin{bmatrix} 2 & 1 \\ 3 & \\ \end{bmatrix} & \Rightarrow & \begin{bmatrix} 2 & 1 \\ 3 & 4 \\ \end{bmatrix} \end{matrix}$$ The lineup process is shown above, with each row describing one event. In the first event, the student with ID $1$ leaves, so the empty spot is at row $1$, column $1$. Next, everyone aligns left; the student with ID $2$ moves one step left, and the empty spot moves to row $1$, column $2$. Then everyone aligns forward; the student with ID $4$ moves one step up, and the empty spot moves to row $2$, column $2$. Finally, the student with ID $1$ returns and fills the empty spot. 【Constraints and Notes】 | Test point ID | $n$ | $m$ | $q$ | Other notes | | :----------: | :----------: | :----------: | :----------: | :----------: | | $1\sim 6$ | $\le 10^3$ | $\le 10^3$ | $\le 500$ | None | | $7\sim 10$ | $\le 5\times 10^4$ | $\le 5\times 10^4$ | $\le 500$ | None | | $11\sim 12$ | $=1$ | $\le 10^5$ | $\le 10^5$ | All events have $x=1$ | | $13\sim 14$ | $=1$ | $\le 3\times 10^5$ | $\le 3\times 10^5$ | All events have $x=1$ | | $15\sim 16$ | $\le 3\times 10^5$ | $\le 3\times 10^5$ | $\le 3\times 10^5$ | All events have $x=1$ | | $17\sim 18$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | None | | $19\sim 20$ | $\le 3\times 10^5$ | $\le 3\times 10^5$ | $\le 3\times 10^5$ | None | The testdata guarantees that each event satisfies $1 \le x \le n,1 \le y \le m$. Translated by ChatGPT 5