首页 > 代码库 > Codeforces Round #401 (Div. 2) C. Alyona and Spreadsheet

Codeforces Round #401 (Div. 2) C. Alyona and Spreadsheet

题目链接:C. Alyona and Spreadsheet

题意:

给你一个n*m的矩阵,现在有k个询问,每次给你一个l,r,问你在[l,r]这行中能否有一列数十非递减的顺序

题解:

用vector来保存矩阵。

对于每一行n*m dp一下最远能达到的范围,然后询问的时候就判断l,r是否在这个范围内。

技术分享
 1 #include<bits/stdc++.h>
 2 #define pb push_back
 3 #define rs m+1,r,rt<<1|1
 4 #define mst(a,b) memset(a,b,sizeof(a))
 5 #define F(i,a,b) for(int i=a;i<=b;++i)
 6 #define ___ freopen("d:\\acm\\input.txt","r",stdin);
 7 using namespace std;
 8 typedef long long ll;
 9 
10 vector<vector<int> >a;
11 vector<vector<int> >dp;
12 vector<int>mx;
13 int n,m,x;
14 
15 int main(){
16     scanf("%d%d",&n,&m);
17     a.resize(n+2),dp.resize(n+2),mx.resize(n+2);
18     F(i,0,n)a[i].resize(m+2),dp[i].resize(m+2);
19     F(i,1,n)F(j,1,m)scanf("%d",&x),a[i][j]=x;
20     F(i,1,m)dp[1][i]=1;
21     F(i,1,n)mx[i]=0;
22     F(i,2,n)F(j,1,m)
23     if(a[i][j]>=a[i-1][j])dp[i][j]=dp[i-1][j]+1;
24     else dp[i][j]=1;
25     F(i,1,n)F(j,1,m)mx[i]=max(mx[i],dp[i][j]);
26     int q;
27     scanf("%d",&q);
28     while(q--)
29     {
30         int x,y;
31         scanf("%d%d",&x,&y);
32         if(y-x+1<=mx[y])puts("Yes");else puts("No");
33     }
34     return 0;
35 }
View Code

 

Codeforces Round #401 (Div. 2) C. Alyona and Spreadsheet