{"problem":{"name":"C. Alyona and Spreadsheet","description":{"content":"During the lesson small girl Alyona works with one famous spreadsheet computer program and learns how to edit tables. Now she has a table filled with integers. The table consists of _n_ rows and _m_ ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF777C"},"statements":[{"statement_type":"Markdown","content":"During the lesson small girl Alyona works with one famous spreadsheet computer program and learns how to edit tables.\n\nNow she has a table filled with integers. The table consists of _n_ rows and _m_ columns. By _a__i_, _j_ we will denote the integer located at the _i_\\-th row and the _j_\\-th column. We say that the table is sorted in non-decreasing order in the column _j_ if _a__i_, _j_ ≤ _a__i_ + 1, _j_ for all _i_ from 1 to _n_ - 1.\n\nTeacher gave Alyona _k_ tasks. For each of the tasks two integers _l_ and _r_ are given and Alyona has to answer the following question: if one keeps the rows from _l_ to _r_ inclusive and deletes all others, will the table be sorted in non-decreasing order in at least one column? Formally, does there exist such _j_ that _a__i_, _j_ ≤ _a__i_ + 1, _j_ for all _i_ from _l_ to _r_ - 1 inclusive.\n\nAlyona is too small to deal with this task and asks you to help!\n\n## Input\n\nThe first line of the input contains two positive integers _n_ and _m_ (1 ≤ _n_·_m_ ≤ 100 000) — the number of rows and the number of columns in the table respectively. Note that your are given a constraint that bound the product of these two integers, i.e. the number of elements in the table.\n\nEach of the following _n_ lines contains _m_ integers. The _j_\\-th integers in the _i_ of these lines stands for _a__i_, _j_ (1 ≤ _a__i_, _j_ ≤ 109).\n\nThe next line of the input contains an integer _k_ (1 ≤ _k_ ≤ 100 000) — the number of task that teacher gave to Alyona.\n\nThe _i_\\-th of the next _k_ lines contains two integers _l__i_ and _r__i_ (1 ≤ _l__i_ ≤ _r__i_ ≤ _n_).\n\n## Output\n\nPrint \"_Yes_\" to the _i_\\-th line of the output if the table consisting of rows from _l__i_ to _r__i_ inclusive is sorted in non-decreasing order in at least one column. Otherwise, print \"_No_\".\n\n[samples]\n\n## Note\n\nIn the sample, the whole table is not sorted in any column. However, rows 1–3 are sorted in column 1, while rows 4–5 are sorted in column 3.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"在课堂上，小女孩 Alyona 正在使用一款著名的电子表格程序，并学习如何编辑表格。\n\n现在她有一个填满整数的表格。该表格包含 #cf_span[n] 行和 #cf_span[m] 列。我们用 #cf_span[ai, j] 表示位于第 #cf_span[i] 行和第 #cf_span[j] 列的整数。我们称表格在第 #cf_span[j] 列中按非递减顺序排序，当且仅当对所有从 #cf_span[1] 到 #cf_span[n - 1] 的 #cf_span[i]，都有 #cf_span[ai, j ≤ ai + 1, j]。\n\n老师给了 Alyona #cf_span[k] 个任务。对于每个任务，给定两个整数 #cf_span[l] 和 #cf_span[r]，Alyona 需要回答如下问题：如果仅保留从第 #cf_span[l] 行到第 #cf_span[r] 行（包含两端），并删除其余所有行，那么表格是否至少在一列中按非递减顺序排序？形式化地说，是否存在某一列 #cf_span[j]，使得对所有从 #cf_span[l] 到 #cf_span[r - 1] 的 #cf_span[i]，都有 #cf_span[ai, j ≤ ai + 1, j]。\n\nAlyona 太小，无法处理这个任务，因此她请求你的帮助！\n\n输入的第一行包含两个正整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n·m ≤ 100 000]）——分别表示表格的行数和列数。请注意，题目给出了这两个整数的乘积的约束，即表格中元素的总数。\n\n接下来的 #cf_span[n] 行，每行包含 #cf_span[m] 个整数。第 #cf_span[i] 行中的第 #cf_span[j] 个整数表示 #cf_span[ai, j]（#cf_span[1 ≤ ai, j ≤ 10^9]）。\n\n下一行包含一个整数 #cf_span[k]（#cf_span[1 ≤ k ≤ 100 000]）——老师给 Alyona 的任务数量。\n\n接下来的 #cf_span[k] 行中，第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ n]）。\n\n如果由第 #cf_span[li] 行到第 #cf_span[ri] 行（包含两端）组成的表格至少在一列中按非递减顺序排序，则在输出的第 #cf_span[i] 行打印 \"_Yes_\"；否则打印 \"_No_\"。\n\n在样例中，整个表格在任何一列中都没有排序。然而，第 1–3 行在第 #cf_span[1] 列中是排序的，而第 4–5 行在第 #cf_span[3] 列中是排序的。\n\n## Input\n\n输入的第一行包含两个正整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n·m ≤ 100 000]）——分别表示表格的行数和列数。请注意，题目给出了这两个整数的乘积的约束，即表格中元素的总数。接下来的 #cf_span[n] 行，每行包含 #cf_span[m] 个整数。第 #cf_span[i] 行中的第 #cf_span[j] 个整数表示 #cf_span[ai, j]（#cf_span[1 ≤ ai, j ≤ 10^9]）。下一行包含一个整数 #cf_span[k]（#cf_span[1 ≤ k ≤ 100 000]）——老师给 Alyona 的任务数量。接下来的 #cf_span[k] 行中，第 #cf_span[i] 行包含两个整数 #cf_span[li] 和 #cf_span[ri]（#cf_span[1 ≤ li ≤ ri ≤ n]）。\n\n## Output\n\n如果由第 #cf_span[li] 行到第 #cf_span[ri] 行（包含两端）组成的表格至少在一列中按非递减顺序排序，则在输出的第 #cf_span[i] 行打印 \"_Yes_\"；否则打印 \"_No_\"。\n\n[samples]\n\n## Note\n\n在样例中，整个表格在任何一列中都没有排序。然而，第 1–3 行在第 #cf_span[1] 列中是排序的，而第 4–5 行在第 #cf_span[3] 列中是排序的。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of rows and columns of a table.  \nLet $ A = (a_{i,j}) \\in \\mathbb{Z}^{n \\times m} $ be the table, where $ a_{i,j} $ is the element in row $ i $, column $ j $.  \n\nFor each column $ j \\in \\{1, \\dots, m\\} $, define the *column-wise sortedness* predicate:  \n$$\n\\text{sorted}(j, l, r) := \\forall i \\in \\{l, \\dots, r-1\\}, \\; a_{i,j} \\leq a_{i+1,j}\n$$\n\n**Constraints**  \n1. $ 1 \\leq n \\cdot m \\leq 100{,}000 $  \n2. $ 1 \\leq a_{i,j} \\leq 10^9 $ for all $ i \\in \\{1, \\dots, n\\}, j \\in \\{1, \\dots, m\\} $  \n3. $ 1 \\leq k \\leq 100{,}000 $  \n4. For each query $ i \\in \\{1, \\dots, k\\} $: $ 1 \\leq l_i \\leq r_i \\leq n $\n\n**Objective**  \nFor each query $ (l_i, r_i) $, determine:  \n$$\n\\exists j \\in \\{1, \\dots, m\\} \\text{ such that } \\text{sorted}(j, l_i, r_i)\n$$  \nOutput \"Yes\" if true, \"No\" otherwise.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF777C","tags":["binary search","data structures","dp","greedy","implementation","two pointers"],"sample_group":[["5 4\n1 2 3 5\n3 1 3 2\n4 5 2 3\n5 5 3 2\n4 4 3 4\n6\n1 1\n2 5\n4 5\n3 5\n1 3\n1 5","Yes\nNo\nYes\nYes\nYes\nNo"]],"created_at":"2026-03-03 11:00:39"}}