Alyona and Spreadsheet
Hazrat Ali
Now she has a table filled with integers. The table consists of n rows and m columns. By ai, 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 ai, j ≤ ai + 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 ai, j ≤ ai + 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 ≤ 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.
Each of the following n lines contains m integers. The j-th integers in the i of these lines stands for ai, j (1 ≤ ai, j ≤ 109).
The next line of the input contains an integer k (1 ≤ k ≤ 100 000) — the number of task that teacher gave to Alyona.
The i-th of the next k lines contains two integers li and ri (1 ≤ li ≤ ri ≤ n).
Print "Yes" to the i-th line of the output if the table consisting of rows from li to ri inclusive is sorted in non-decreasing order in at least one column. Otherwise, print "No".
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
Yes
No
Yes
Yes
Yes
No
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int g[n][m];
for (int r = 0; r < n; r++)
{
for (int c = 0; c < m; c++)
{
cin >> g[r][c];
}
}
int b[n][m];
for (int c = 0; c < m; c++)
{
for (int r = 0; r < n; r++)
{
b[r][c] = (r == 0) or (g[r - 1][c] <= g[r][c]);
}
}
int ps[n][m];
for (int c = 0; c < m; c++)
{
for (int r = 0; r < n; r++)
{
ps[r][c] = (r == 0) ? b[r][c] : b[r][c] + ps[r - 1][c];
}
}
int k;
cin >> k;
map<int, map<int, int>> memo;
while (k--)
{
int L, R;
cin >> L >> R;
L--, R--;
if (memo.count(L) == 0 or memo[L].count(R) == 0)
{
bool ok = false;
for (int c = 0; c < m; c++)
{
if (ps[R][c] - ps[L][c] == R - L)
{
ok = true;
break;
}
}
memo[L][R] = ok;
}
if (memo[L][R])
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
}
return 0;
}