P7220 [JOISC 2020] Sweeping

JOISC2020 Day 1 T3. If Luogu’s built-in download function cannot download the wrong test points, you can download the data yourself [here](https://www.ioi-jp.org/camp/2020/2020-sp-tasks/day1/sweeping-data.zip). Since the testdata is too large, when judging this problem, the judge machine may need 30 seconds to load the data. Please note the unusual time and memory limits of this problem.

Since Bitaro got AK at IOI, the IOI organizers gave him a house. The room is an isosceles right triangle with leg length $N$. Any point in the room is represented by coordinates $(x,y)$, where $0\leq x+y\leq N$. The right-angle vertex is at the origin, and the two legs of the triangle are the $x$-axis and the $y$-axis.  One day, Bitaro found that he had already AK’ed $1919810$ IOIs, so he had nothing to do and decided to clean the dust in the room. Initially there are $M$ piles of dust, and the $i$-th pile is at $(X_i,Y_i)$. Also, it is possible that multiple piles of dust are at the same position. Now Bitaro is going to sweep the room using a broom. We model the broom as a line segment placed in the room, and we call the length of this segment the broom’s width. Since Bitaro is very organized, he will only clean the room in the following two ways: - Bitaro places the broom parallel to the $y$-axis, with one endpoint at the origin. Then he moves the broom to the right perpendicularly until it cannot move any further. If the broom’s width is $l$, then any dust pile originally at $(x,y)$ satisfying $x

The first line contains three integers $N,M,Q$. The next $m$ lines each contain two integers $X_i,Y_i$, representing the initial position of the $i$-th dust pile. The next $Q$ lines each contain two or three integers, describing an event. Let $T_i$ be the first integer of the line. The meaning of each line is as follows: - If $T_i=1$, then the line contains two integers $T_i,P_i$, meaning Bitaro queries the coordinates of the $P_i$-th dust pile. - If $T_i=2$, then the line contains two integers $T_i,L_i$, meaning Bitaro performs process H using a broom of width $L_i$. - If $T_i=3$, then the line contains two integers $T_i,L_i$, meaning Bitaro performs process V using a broom of width $L_i$. - If $T_i=4$, then the line contains three integers $T_i,A_i,B_i$, meaning a new dust pile appears at position $(A_i,B_i)$.

For each event with $T_i=1$, output one line with two integers, representing the coordinates of the $P_i$-th dust pile at the time event $i$ happens.

### Sample 1 Explanation At the beginning, the first dust pile is at $(1,1)$ and the second dust pile is at $(4,0)$. Figure 1 shows the current state of the room.  In the first event, the third dust pile is added at $(2,3)$. Figure 2 shows the current state of the room.  In the second event, Bitaro performs process V with a broom of width $3$. After that, the first dust pile moves to $(1,3)$. Figure 3 shows the current state of the room.  In the third event, Bitaro queries the coordinates of the first dust pile, which are $(1,3)$. In the fourth event, the fourth dust pile is added at $(1,2)$. Figure 4 shows the current state of the room.  In the fifth event, Bitaro performs process H with a broom of width $3$. The first dust pile moves to $(3,3)$, the third dust pile moves to $(3,3)$, and the fourth dust pile moves to $(3,2)$. Figure 5 shows the current state of the room.  In the sixth event, Bitaro performs process H with a broom of width $0$. The second dust pile moves to $(6,0)$. Figure 6 shows the current state of the room.  In the seventh event, Bitaro queries the coordinates of the fourth dust pile, which are $(3,2)$. In the eighth event, Bitaro performs process V with a broom of width $2$, but nothing happens. Figure 7 shows the current state of the room.  In the ninth event, Bitaro queries the coordinates of the third dust pile, which are $(3,3)$. In the tenth event, Bitaro queries the coordinates of the second dust pile, which are $(6,0)$. This sample satisfies the limits of Subtask 1 and Subtask 5. #### Sample 2 to 5 Explanation The second sample satisfies the limits of Subtask 1, 2, 4, and 5. The third sample satisfies the limits of Subtask 1, 2, and 5. The fourth sample satisfies the limits of Subtask 1, 3, 4, and 5. The fifth sample satisfies the limits of Subtask 1 and Subtask 5. #### Subtasks | Subtask ID | Special Property | Score | | :----------: | :----------: | :----------: | | Subtask 1 | $m\leq 2\times 10^3,Q\leq 5\times 10^3$ | $1$ | | Subtask 2 | $T\in\{1,2,4\}$ | $10$ | | Subtask 3 | $T\in\{1,2,3\},X_i\leq X_{i+1},Y_i\geq Y_{i+1}(1\leq i\leq m-1)$ | $11$ | | Subtask 4 | $T\in\{1,2,3\}$ | $53$ | | Subtask 5 | None | $25$ | For $100\%$ of the data, $1\leq n\leq 10^9,1\leq m\leq 5\times 10^5,1\leq Q\leq 10^6$. It is guaranteed that: - $0\leq X_i,Y_i\leq N,X_i+Y_i\leq N(1\leq i\leq m)$. - $1\leq P_i\leq M^\prime(1\leq i\leq Q)$, where $M^\prime$ is the number of dust piles at the time event $i$ happens. - $0\leq L_i\leq n-1(1\leq i\leq Q)$. - $0\leq A_i,B_i\leq n,A_i+B_i\leq n(1\leq i\leq Q)$. - There is at least one event with $T_i=1$. Translated by ChatGPT 5