fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int MAX_M = 1005;
  5. const int MAX_N = 1005;
  6.  
  7. int m, n, k;
  8. int a[MAX_M][MAX_N];
  9. int is01[MAX_M][MAX_N], is12[MAX_M][MAX_N];
  10. pair<int, int> queries[1000006];
  11. unordered_map<long long, int> cache;
  12.  
  13. // Hàm tính largest rectangle trong histogram
  14. int largestRectangleArea(vector<int> &height) {
  15.     stack<int> st;
  16.     int maxArea = 0, n = height.size();
  17.     height.push_back(0); // sentinel
  18.  
  19.     for (int i = 0; i <= n; ++i) {
  20.         while (!st.empty() && height[i] < height[st.top()]) {
  21.             int h = height[st.top()]; st.pop();
  22.             int w = st.empty() ? i : i - st.top() - 1;
  23.             maxArea = max(maxArea, h * w);
  24.         }
  25.         st.push(i);
  26.     }
  27.  
  28.     height.pop_back();
  29.     return maxArea;
  30. }
  31.  
  32. // Tính diện tích lớn nhất trong khoảng dòng [p, q]
  33. int solve(int p, int q) {
  34.     vector<int> height(n, 0);
  35.     int res = 0;
  36.  
  37.     // Trường hợp tập {0,1}
  38.     for (int i = p; i <= q; ++i) {
  39.         for (int j = 0; j < n; ++j)
  40.             height[j] = is01[i][j] ? height[j] + 1 : 0;
  41.         res = max(res, largestRectangleArea(height));
  42.     }
  43.  
  44.     fill(height.begin(), height.end(), 0);
  45.  
  46.     // Trường hợp tập {1,2}
  47.     for (int i = p; i <= q; ++i) {
  48.         for (int j = 0; j < n; ++j)
  49.             height[j] = is12[i][j] ? height[j] + 1 : 0;
  50.         res = max(res, largestRectangleArea(height));
  51.     }
  52.  
  53.     return res;
  54. }
  55.  
  56. int main() {
  57.     ios::sync_with_stdio(false);
  58.     cin.tie(0);
  59.     freopen("SQL.inp","r",stdin);
  60.     freopen("SQL.out","w",stdout);
  61.     cin >> m >> n;
  62.     for (int i = 0; i < m; ++i)
  63.         for (int j = 0; j < n; ++j) {
  64.             cin >> a[i][j];
  65.             is01[i][j] = (a[i][j] == 0 || a[i][j] == 1);
  66.             is12[i][j] = (a[i][j] == 1 || a[i][j] == 2);
  67.         }
  68.  
  69.     cin >> k;
  70.     for (int i = 0; i < k; ++i) {
  71.         int p, q;
  72.         cin >> p >> q;
  73.         --p; --q; // 0-index
  74.         queries[i] = {p, q};
  75.     }
  76.  
  77.     for (int i = 0; i < k; ++i) {
  78.         int p = queries[i].first, q = queries[i].second;
  79.         long long key = 1LL * p * 10000 + q; // tạo key duy nhất
  80.         if (cache.count(key)) {
  81.             cout << cache[key] << '\n';
  82.         } else {
  83.             int res = solve(p, q);
  84.             cache[key] = res;
  85.             cout << res << '\n';
  86.         }
  87.     }
  88.  
  89.     return 0;
  90. }
  91.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6TaC9N
language:
C++ (gcc 8.3)
created:
9 days ago
visibility:
public

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!