D. Animals and Puzzle

Codeforces

IDCF713D

Time5000ms

Memory512MB

Difficulty—

binary searchdata structures

English · Original

Chinese · Translation

Formal · Original

Owl Sonya gave a huge lake puzzle of size _n_ × _m_ to hedgehog Filya as a birthday present. Friends immediately started to assemble the puzzle, but some parts of it turned out to be empty — there was no picture on them. Parts with picture on it are denoted by 1, while empty parts are denoted by 0. Rows of the puzzle are numbered from top to bottom with integers from 1 to _n_, while columns are numbered from left to right with integers from 1 to _m_. Animals decided to complete the picture and play with it, as it might be even more fun! Owl and hedgehog ask each other some queries. Each query is provided by four integers _x_1, _y_1, _x_2, _y_2 which define the rectangle, where (_x_1, _y_1) stands for the coordinates of the up left cell of the rectangle, while (_x_2, _y_2) stands for the coordinates of the bottom right cell. The answer to the query is the size of the maximum **square** consisting of picture parts only (only parts denoted by 1) and located fully inside the query rectangle. Help Sonya and Filya answer _t_ queries. ## Input The first line of the input contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 1000) — sizes of the puzzle. Each of the following _n_ lines contains _m_ integers _a__ij_. Each of them is equal to 1 if the corresponding cell contains a picture and 0 if it's empty. Next line contains an integer _t_ (1 ≤ _t_ ≤ 1 000 000) — the number of queries. Then follow _t_ lines with queries' descriptions. Each of them contains four integers _x_1, _y_1, _x_2, _y_2 (1 ≤ _x_1 ≤ _x_2 ≤ _n_, 1 ≤ _y_1 ≤ _y_2 ≤ _m_) — coordinates of the up left and bottom right cells of the query rectangle. ## Output Print _t_ lines. The _i_\-th of them should contain the maximum size of the square consisting of 1\-s and lying fully inside the query rectangle. [samples]

猫头鹰索尼娅送给刺猬菲利亚一个大小为 $n × m$ 的巨型拼图作为生日礼物。朋友们立即开始拼图，但其中一些部分是空的——上面没有图案。有图案的部分用 $1$ 表示，空的部分用 $0$ 表示。拼图的行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。动物们决定完成图案并一起玩，这可能会更有趣！猫头鹰和刺猬互相提问。每个查询由四个整数 $x1$、$y1$、$x2$、$y2$ 定义，表示一个矩形区域，其中 $(x1, y1)$ 是矩形的左上角单元格坐标，$(x2, y2)$ 是矩形的右下角单元格坐标。查询的答案是完全位于该查询矩形内的、仅由图案部分（即值为 $1$ 的部分）组成的最大正方形的边长。请帮助索尼娅和菲利亚回答 $t$ 个查询。输入的第一行包含两个整数 $n$ 和 $m$ ($1 ≤ n, m ≤ 1000$) —— 拼图的尺寸。接下来的 $n$ 行每行包含 $m$ 个整数 $a_{ij}$。每个整数等于 $1$ 表示对应单元格有图案，等于 $0$ 表示为空。下一行包含一个整数 $t$ ($1 ≤ t ≤ 1 000 000$) —— 查询的数量。随后是 $t$ 行查询描述，每行包含四个整数 $x1$、$y1$、$x2$、$y2$ ($1 ≤ x1 ≤ x2 ≤ n$, $1 ≤ y1 ≤ y2 ≤ m$) —— 查询矩形的左上角和右下角单元格坐标。请输出 $t$ 行。第 $i$ 行应包含完全位于查询矩形内的、仅由 $1$ 组成的最大正方形的边长。 ## Input 输入的第一行包含两个整数 $n$ 和 $m$ ($1 ≤ n, m ≤ 1000$) —— 拼图的尺寸。接下来的 $n$ 行每行包含 $m$ 个整数 $a_{ij}$。每个整数等于 $1$ 表示对应单元格有图案，等于 $0$ 表示为空。下一行包含一个整数 $t$ ($1 ≤ t ≤ 1 000 000$) —— 查询的数量。随后是 $t$ 行查询描述，每行包含四个整数 $x1$、$y1$、$x2$、$y2$ ($1 ≤ x1 ≤ x2 ≤ n$, $1 ≤ y1 ≤ y2 ≤ m$) —— 查询矩形的左上角和右下角单元格坐标。 ## Output 请输出 $t$ 行。第 $i$ 行应包含完全位于查询矩形内的、仅由 $1$ 组成的最大正方形的边长。 [samples]

Let $ A \in \{0,1\}^{n \times m} $ be a binary matrix representing the puzzle, where $ A[i][j] = 1 $ if cell $ (i,j) $ contains a picture, and $ 0 $ otherwise. For a query $ (x_1, y_1, x_2, y_2) $, define the submatrix $ R = A[x_1:x_2, y_1:y_2] $ (inclusive). Let $ S(R) $ denote the side length of the largest square submatrix of $ R $ consisting entirely of 1s. For each query, output $ \max \{ k \in \mathbb{N} : \exists\ (i,j) \text{ s.t. } x_1 \leq i \leq x_2 - k + 1,\ y_1 \leq j \leq y_2 - k + 1,\ \forall\ a,b \in [0,k-1],\ A[i+a][j+b] = 1 \} $. Given $ t $ such queries, compute $ S(R) $ for each.

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "D. Animals and Puzzle",
    "description": {
      "content": "Owl Sonya gave a huge lake puzzle of size _n_ × _m_ to hedgehog Filya as a birthday present. Friends immediately started to assemble the puzzle, but some parts of it turned out to be empty — there was",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 5000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF713D"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Owl Sonya gave a huge lake puzzle of size _n_ × _m_ to hedgehog Filya as a birthday present. Friends immediately started to assemble the puzzle, but some parts of it turned out to be empty — there was...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "猫头鹰索尼娅送给刺猬菲利亚一个大小为 $n × m$ 的巨型拼图作为生日礼物。朋友们立即开始拼图，但其中一些部分是空的——上面没有图案。有图案的部分用 $1$ 表示，空的部分用 $0$ 表示。拼图的行从上到下编号为 $1$ 到 $n$，列从左到右编号为 $1$ 到 $m$。\n\n动物们决定完成图案并一起玩，这可能会更有趣！猫头鹰和刺猬互相提问。每个查询由四个整数 $x1$、$y1$、$x2$、$y2...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Let $ A \\in \\{0,1\\}^{n \\times m} $ be a binary matrix representing the puzzle, where $ A[i][j] = 1 $ if cell $ (i,j) $ contains a picture, and $ 0 $ otherwise.\n\nFor a query $ (x_1, y_1, x_2, y_2) $, d...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments