|
Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
ℹ️ We've recently migrated MOG to a new server with a different grader. As a result, some features—especially those related to submission evaluation—might not work correctly. If you encounter any issues, please report them by clicking the exclamation icon in the bottom right corner of the website.
D - Daunting device
Languages: C, C++, Java, Haskell, Pascal, Python, JavaScript, Tiger, C#
Time & Memory limits: (details)
In a recent trip to an excavation site in the Caribbean island of Saint Basil, you found a mysterious device with some instructions resembling a puzzle. Your local guide Vibenas tells you that if you solve the puzzle, the device might show you the place where a big treasure left by the old merciless pirate Lyerpes is hidden.
The device has a tape with $L$ cells indexed from $0$ to $L - 1$. Each cell has a color than can be changed with commands to the device. Each color is encoded by an integer, and initially all cells have the same color. The instructions that you found represent $N$ steps to be performed before the device shows the way to the treasure. Each step is described using four integers $P$, $X$, $A$ and $B$. The instructions say that to complete the step you must first count the number of cells currently having color $P$. Let this number be $S$. Then you must calculate the values
$M_1 = (A + S^2) \texttt{ mod } L$,
$M_2 = (A + (S + B)^2) \texttt{ mod } L$,
Finally you have to make all cells within the closed interval $[min(M_1, M_2 ), max(M_1, M_2 )]$ to be of color $X$.
After the exhausting task of processing the $N$ steps required by the device, you still have one job: given a color that appears the greatest number of times in the device tape after all steps (that is, a most frequent color), you must go to the shipwreck of Lyerpes’ legendary vessel and say aloud the number of cells having that color. Note that this number is unique even if more than one color appears the greatest number of times in the device tape after all steps.
Doing all those calculations on the device will take ages but you, as a renowned programmer, can create a program that quickly indicates the answer for the puzzle. After that, the real hard part of your mission will be to find out where is the shipwreck of Lyerpes’ old vessel.
Input
The first line contains three integers $L$, $C$ and $N$ ($1 \leq L, C, N \leq 10^5$), representing respectively the number of cells in the tape, the number of available colors, and the number of steps in the instructions. Colors are identified by distinct integers from $1$ to $C$ and initially all cells have color $1$. Each of the next $N$ lines describes a step of the instructions with four integers $P$, $X$, $A$ and $B$ ($1 \leq P, X \leq C$ and $0 \leq A, B \leq 10^8$), indicating respectively the color whose number of cells is used to decide the range of the step, the color the cells in the range must have after the step is performed, and the other two values used to calculate the bounds of the range as described above.
Output
Given a color that appears the greatest number of times in the device tape after sequentially performing all steps described in the input, output a single line with an integer indicating the number of cells having that color.
Sample test(s)
Input
7 5 2
1 2 5 3
3 3 0 1
Output
4
Input
7 10 8
10 6 5 6
5 1 7 5
9 9 10 1
3 2 6 7
8 3 4 8
3 7 7 4
9 3 9 7
1 1 8 1000
Output
3