Integers on Grid

AtCoder

IDabc224_e

Time2000ms

Memory256MB

Difficulty—

We have a grid with $H$ horizontal rows and $W$ vertical columns. Let $(i, j)$ denote the square at the $i$\-th row from the top and $j$\-th column from the left. Each square contains an integer. For each $i = 1, 2, \ldots, N$, the square $(r_i, c_i)$ contains a positive integer $a_i$. The other square contains a $0$. Initially, there is a piece on the square $(R, C)$. Takahashi can move the piece to a square other than the square it occupies now, any number of times. However, when moving the piece, both of the following conditions must be satisfied. * The integer written on the square to which the piece is moved is strictly greater than the integer written on the square from which the piece is moved. * The squares to and from which the piece is moved are in the same row or the same column. For each $i = 1, 2, \ldots, N$, print the maximum number of times Takahashi can move the piece when $(R, C) = (r_i, c_i)$. ## Constraints * $2 \leq H, W \leq 2 \times 10^5$ * $1 \leq N \leq \min(2 \times 10^5, HW)$ * $1 \leq r_i \leq H$ * $1 \leq c_i \leq W$ * $1 \leq a_i \leq 10^9$ * $i \neq j \Rightarrow (r_i, c_i) \neq (r_j, c_j)$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $H$ $W$ $N$ $r_1$ $c_1$ $a_1$ $r_2$ $c_2$ $a_2$ $\vdots$ $r_N$ $c_N$ $a_N$ [samples]

Samples

Input #1

Output #1

1
0
2
0
3
1
0

The grid contains the following integers.

4 7 0
3 0 5
2 5 5

*   When $(R, C) = (r_1, c_1) = (1, 1)$, you can move the piece once by moving it as $(1, 1) \rightarrow (1, 2)$.
*   When $(R, C) = (r_2, c_2) = (1, 2)$, you cannot move the piece at all.
*   When $(R, C) = (r_3, c_3) = (2, 1)$, you can move the piece twice by moving it as $(2, 1) \rightarrow (1, 1) \rightarrow (1, 2)$.
*   When $(R, C) = (r_4, c_4) = (2, 3)$, you cannot move the piece at all.
*   When $(R, C) = (r_5, c_5) = (3, 1)$, you can move the piece three times by moving it as $(3, 1) \rightarrow (2, 1) \rightarrow (1, 1) \rightarrow (1, 2)$.
*   When $(R, C) = (r_6, c_6) = (3, 2)$, you can move the piece once by moving it as $(3, 2) \rightarrow (1, 2)$.
*   When $(R, C) = (r_7, c_7) = (3, 3)$, you cannot move the piece at all.

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Integers on Grid",
    "description": {
      "content": "We have a grid with $H$ horizontal rows and $W$ vertical columns. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left. Each square contains an integer. For ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc224_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have a grid with $H$ horizontal rows and $W$ vertical columns. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left.\nEach square contains an integer. For ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments