fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int histogram(vector<int> &v, int m) {
  5. 	int n = (int) v.size();
  6. 	vector<int> pref(n);
  7. 	for(int i = 1; i < n; i++) {
  8. 		pref[i] = pref[i - 1] + (v[i] < 0);
  9. 	}
  10. 	int area = 0;
  11. 	stack<int> st;
  12. 	for(int i = 0; i < n; i++) {
  13. 		while(!st.empty() and abs(v[st.top()]) > abs(v[i])) {
  14. 			int u = st.top();
  15. 			st.pop();
  16. 			int start = st.empty() ? -1 : st.top();
  17. 			int minus = pref[i - 1] - (start <= 0 ? 0 : pref[start - 1]);	
  18. 			area = max(area, (i - start - 1 - minus) * abs(v[u]));
  19. 		}
  20. 		st.push(i);
  21. 	}
  22. 	while(!st.empty()) {
  23. 		int u = st.top();
  24. 		st.pop();
  25. 		int start = st.empty() ? -1 : st.top();
  26. 		int minus = pref[n - 1] - (start <= 0 ? 0 : pref[start - 1]);	
  27. 		area = max(area, (n - start - 1 - minus) * abs(v[u]));
  28. 	}
  29. 	return area;
  30. }
  31.  
  32. int main() {
  33. 	int T;
  34. 	cin >> T;
  35. 	while(T--) {
  36. 		int n, m;
  37. 		cin >> n >> m;
  38. 		vector<vector<int>> a(n, vector<int> (m));
  39. 		for(int i = 0; i < n; i++) {
  40. 			for(int j = 0; j < m; j++) {
  41. 				cin >> a[i][j];
  42. 			}
  43. 		}
  44.  
  45. 		vector<vector<int>> col(n, vector<int> (m, 1));
  46. 		for(int j = 0; j < m; j++) {
  47. 			for(int i = 1; i < n; i++) {
  48. 				if(a[i][j] > a[i - 1][j]) {
  49. 					col[i][j] += col[i - 1][j];
  50. 				}
  51. 			}
  52. 		}
  53.  
  54. 		vector<int> check(m, -1);
  55. 		int sol = 0;
  56. 		for(int i = 0; i < n; i++) {
  57. 			vector<int> v;
  58. 			for(int j = 1; j < m; j++) {
  59. 				if(a[i][j] <= a[i][j - 1]) {
  60. 					check[j] = i;
  61. 				}
  62. 			}
  63. 			for(int j = 0; j < m; j++) {
  64. 				if(j == 0) {
  65. 					v.push_back(col[i][j]);
  66. 				}
  67. 				else {
  68. 					int last = check[j];
  69. 					v.push_back(min(col[i][j], i - last));
  70. 					v.back() *= -1;
  71. 					v.push_back(col[i][j]);
  72. 				}
  73. 			}
  74. 			sol = max(sol, histogram(v, m));
  75. 		}
  76. 		cout << sol << '\n';
  77. 	}
  78.  
  79. 	return 0;
  80. }
  81.  
Success #stdin #stdout 0s 5292KB
comments (?)
stdin
copy 
4
3 3
3 0 4
1 2 5
4 6 7
3 3
1 2 5
4 6 7
10 8 3
5 5
2 5 3 8 3
1 4 6 8 4
3 6 7 9 5
1 3 6 4 2
2 6 4 3 1
4  4
1 2 5 6
2 3 4 7
3 4 5 8
8 9 10 100
stdout
copy 
6
6
8
12
https://ideone.com/V0Kwc5
row wise and col wise sorted area
language:
C++ 4.3.2 (gcc-4.3.2)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!