【CodeForces 777C】Alyona and Spreadsheet

Alyona and Spreadsheet

Problem Description

Duringthe lesson small girl Alyona works with one famous spreadsheet computer programand learns how to edit tables.

Nowshe has a table filled with integers. The table consists ofnrows andmcolumns. Byai, jwe will denote the integerlocated at thei-th row and the j-th column. We say that thetable is sorted in non-decreasing order in the columnjifai, j ≤ ai + 1, jfor allifrom1ton - 1.

Teacher gave Alyonaktasks. For each of thetasks two integerslandrare given and Alyona has toanswer the following question: if one keeps the rows from l to r inclusive and deletes allothers, will the table be sorted in non-decreasing order in at least onecolumn? Formally, does there exist suchjthatai, j ≤ ai + 1, jfor allifromltor - 1inclusive.

Alyona is too small to deal with this task and asks you to help!

Input

The first line of the input contains two positive integersnandm(1 ≤ n·m ≤ 100 000) —the number of rows and the number of columns in the table respectively. Notethat 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 Iof these lines stands forai, j(1 ≤ ai, j ≤ 109).

The next line of the input contains an integerk(1 ≤ k ≤ 100 000) —the number of task that teacher gave to Alyona.

Thei-th of the next k lines contains two integers liandri(1 ≤ li ≤ ri ≤ n).

Output

Print "Yes" tothe i-th line of theoutput if the table consisting of rows from litoriinclusiveis sorted in non-decreasing order in at least one column. Otherwise, print "No".

题目大意：

给出n*m的矩阵，k次查询，如果第l行到r行至少有一列是非递减的，则输出Yes，否则输出No

思路：

预处理每行能到达最大行是多少，再O(1)查询，注意把每列能到达的最大行保存一下，减少循环次数（否则会T）

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define manx 100005 using namespace std; int c[manx],d[manx]; int main() { int n,m; scanf("%d%d",&n,&m); int a[n+5][m+5]={0}; for (int i=1; i<=n; i++) for (int j=1; j<=m; j++) scanf("%d",&a[i][j]); int k,cnt=1; for (int i=1; i<=n; i++){ for (int j=1; j<=m; j++){ k=i; if(d[j] >= i) k=d[j]; //优化 else while(a[k+1][j] >= a[k][j] && k<n) k++; d[j]=k; //d the max of every column c[cnt]=max(k,c[cnt]); //c the max of every row } cnt++; } int q,x,y; scanf("%d",&q); for (int i=1; i<=q; i++){ scanf("%d%d",&x,&y); if(c[x] >= y) printf("Yes "); else printf("No "); } return 0; }