A10787. Alyona and Spreadsheet
编程题
普及/提高-
知识点
题目描述
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$ 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$ .
Teacher 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.
Alyona is too small to deal with this task and asks you to help!
Now 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$ .
Teacher 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.
Alyona is too small to deal with this task and asks you to help!
输入格式
The first line of the input contains two positive integers $n$ and $m$ ( $1<=n·m<=100000$ ) — 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.
Each 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}<=10^{9}$ ).
The next line of the input contains an integer $k$ ( $1<=k<=100000$ ) — the number of task that teacher gave to Alyona.
The $i$ -th of the next $k$ lines contains two integers $l_{i}$ and $r_{i}$ ( $1<=l_{i}<=r_{i}<=n$ ).
Each 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}<=10^{9}$ ).
The next line of the input contains an integer $k$ ( $1<=k<=100000$ ) — the number of task that teacher gave to Alyona.
The $i$ -th of the next $k$ lines contains two integers $l_{i}$ and $r_{i}$ ( $1<=l_{i}<=r_{i}<=n$ ).
输出格式
Print "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".
输入输出样例
输入 #1
5 4 1 2 3 5 3 1 3 2 4 5 2 3 5 5 3 2 4 4 3 4 6 1 1 2 5 4 5 3 5 1 3 1 5
输出 #1
Yes No Yes Yes Yes No
说明/提示
In 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$ .