首页 > 代码库 > codeforces 777 C
codeforces 777 C
n*m的一个表
k个查询查询 l 行到 r 行 是否某一列是不递减的
有yes
否组no
显然不能暴力 维护一个到 这一行最大的不递减的 行数
如何维护呢 显然n*m是需要的 然后维护这一列能不能走下去 然后更新一下这个 行数
最后查询的时候 l r 和 这个对应的行数 比一下
#include <iostream> #include<string.h> #include<stdio.h> #include<algorithm> using namespace std ; #define LL long long #define MAXN 1010 int main() { int n,m; scanf("%d%d",&n,&m); int num[n+9][m+9],jud[n+9],cnt[n+9][m+9]; for(int i=1;i<=n;i++) { jud[i]=1; for(int j=1;j<=m;j++) { scanf("%d",&num[i][j]); cnt[1][j]=1; } } for(int i = 2; i <= n; i++) { for(int j = 1; j <= m; j++) { if(num[i][j]>=num[i-1][j]) cnt[i][j]=1+cnt[i-1][j]; else cnt[i][j]=1; jud[i]=max(jud[i],cnt[i][j]); } } int k; scanf("%d",&k); while(k--) { int l,r; scanf("%d%d",&l,&r); if(jud[r]>=r-l+1) printf("Yes\n"); else printf("No\n"); } return 0; }
codeforces 777 C
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。