首页 > 代码库 > Codeforces 777C Alyona and Spreadsheet(思维)
Codeforces 777C Alyona and Spreadsheet(思维)
题目链接 Alyona and Spreadsheet
记a[i][j]为读入的矩阵,c[i][j]为满足a[i][j],a[i - 1][j], a[i - 2][j],......,a[k][j]不上升的k的最小值。
d[i]为max(c[i][j]) (1 <= j <= m)
那么对于每次询问l,r,若d[r] <= l,那么就符合,反之不符。
因为这里只说名了1 <= nm <= 100000,所以二维数组两个维的大小不确定。
数据可能有n=1, m=100000,也可能有n = 100000, m = 1。
所以我把二维数组开成了一维的。
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 #define rep(i, a, b) for(int i(a); i <= (b); ++i) 6 #define INF 1 << 30 7 8 const int N = 100000 + 10; 9 10 int a[N], c[N], d[N]; 11 int n, m, q, x, y; 12 13 int calc(int i, int j){ 14 return (i - 1) * m + j; 15 } 16 17 int main(){ 18 19 scanf("%d%d", &n, &m); 20 rep(i, 1, m) scanf("%d", a + i); 21 rep(i, 1, m) c[calc(1, i)] = 1; 22 rep(i, 2, n){ 23 rep(j, 1, m){ 24 scanf("%d", &x); 25 if (a[j] <= x){ 26 c[calc(i, j)] = c[calc(i - 1, j)]; 27 a[j] = x; 28 } 29 30 else{ 31 c[calc(i, j)] = i; 32 a[j] = x; 33 } 34 } 35 } 36 37 38 rep(i, 1, n) d[i] = INF; 39 rep(i, 1, n){ 40 rep(j, 1, m) d[i] = min(d[i], c[calc(i, j)]); 41 } 42 43 44 scanf("%d", &q); 45 while (q--){ 46 scanf("%d%d", &x, &y); 47 puts(d[y] <= x ? "Yes" : "No"); 48 } 49 50 51 return 0; 52 53 }
Codeforces 777C Alyona and Spreadsheet(思维)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。