首页 > 代码库 > 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 }
Codeforces Round #401 (Div. 2) C. Alyona and Spreadsheet
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。