G. Yet Another Median Task

Codeforces

IDCF10074G

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

You're given a matrix a with n lines and n columns. We define the median of an array the element from the middle position of sorted array. If there are two such positions (n is even), get the element whose position is minimal. Answer q queries of form: what's the median element of a submatrix (x1, y1, x2, y2). Formally, we consider all elements a[i][j] such as x1 <= i <= x2 and y1 <= j <= y2 and add them into a temporary array. Then, get the median of the array. First line of the input contains numbers n (1 ≤ n ≤ 800) and q (1 ≤ q ≤ 1000). Next n lines contain n numbers, describing the 1-based matrix a. All elements from a can fit into an int type. Next q lines contain numbers x1, y1, x2, y2, describing a query (1 ≤ x1 ≤ x2 ≤ n , 1 ≤ y1 ≤ y2 ≤ n) Output q lines, each line to answer a query. ## Input First line of the input contains numbers n (1 ≤ n ≤ 800) and q (1 ≤ q ≤ 1000). Next n lines contain n numbers, describing the 1-based matrix a. All elements from a can fit into an int type. Next q lines contain numbers x1, y1, x2, y2, describing a query (1 ≤ x1 ≤ x2 ≤ n , 1 ≤ y1 ≤ y2 ≤ n) ## Output Output q lines, each line to answer a query. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the dimension of a square matrix $ A = (a_{i,j}) \in \mathbb{Z}^{n \times n} $, with $ 1 \leq i, j \leq n $. Let $ q \in \mathbb{Z}^+ $ be the number of queries. Each query is a 4-tuple $ (x_1, y_1, x_2, y_2) $, with $ 1 \leq x_1 \leq x_2 \leq n $, $ 1 \leq y_1 \leq y_2 \leq n $. For a query $ (x_1, y_1, x_2, y_2) $, define the multiset: $$ S = \{ a_{i,j} \mid x_1 \leq i \leq x_2,\ y_1 \leq j \leq y_2 \} $$ Let $ m = |S| = (x_2 - x_1 + 1)(y_2 - y_1 + 1) $. Let $ S_{\text{sorted}} $ be the non-decreasing sorted version of $ S $. **Constraints** 1. $ 1 \leq n \leq 800 $ 2. $ 1 \leq q \leq 1000 $ 3. $ a_{i,j} \in \mathbb{Z} $, representable as a 32-bit integer 4. For each query: $ 1 \leq x_1 \leq x_2 \leq n $, $ 1 \leq y_1 \leq y_2 \leq n $ **Objective** For each query $ (x_1, y_1, x_2, y_2) $, output the median of $ S $, defined as: $$ \text{median}(S) = S_{\text{sorted}}[\lfloor (m-1)/2 \rfloor] $$ (where indexing is 0-based).

API Response (JSON)

{
  "problem": {
    "name": "G. Yet Another Median Task",
    "description": {
      "content": "You're given a matrix a with n lines and n columns. We define the median of an array the element from the middle position of sorted array. If there are two such positions (n is even), get the element ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10074G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You're given a matrix a with n lines and n columns. We define the median of an array the element from the middle position of sorted array. If there are two such positions (n is even), get the element ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the dimension of a square matrix $ A = (a_{i,j}) \\in \\mathbb{Z}^{n \\times n} $, with $ 1 \\leq i, j \\leq n $.  \nLet $ q \\in \\mathbb{Z}^+ $ be the number ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments