Advertisement
Dang_Quan_10_Tin

HCN HSGHN L9 2021-2022 (Full Table Imple)

Aug 6th, 2022 (edited)
840
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.90 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. constexpr int N = 1e4 + 5;
  5.  
  6. int n, m, k;
  7. int h[N], oldh[N]; // Height of Column, oldh = h'
  8. int L[N], R[N];    // Left Bound and Right Bound
  9. int s[N], l;       // Imple stack
  10. vector<int> X[N];  // X[i] is the list of X on the i-th row
  11.  
  12. void Read()
  13. {
  14.     cin >> n >> m >> k;
  15.  
  16.     for (int i = 1; i <= k; ++i)
  17.     {
  18.         int x, y;
  19.         cin >> x >> y;
  20.  
  21.         X[x].emplace_back(y);
  22.     }
  23. }
  24.  
  25. void Solve()
  26. {
  27.     int ans(0);
  28.  
  29.     for (int i = 1; i <= n; ++i)
  30.     {
  31.         for (int j = 1; j <= m; ++j)
  32.         {
  33.             // Update h_j, oldh_j = h'_j
  34.             ++h[j];
  35.             ++oldh[j];
  36.         }
  37.  
  38.         for (auto j : X[i])
  39.         {
  40.             oldh[j] = h[j]; // consider last(i,j) = 1
  41.             h[j] = 0;       // last(i, j) = (i, j)
  42.         }
  43.  
  44.         l = 0; // Reset Stack
  45.         for (int j = 1; j <= m; ++j)
  46.         {
  47.             while (l && h[s[l]] >= oldh[j]) // Find Left Bound of Rectangle
  48.                 --l;
  49.  
  50.             L[j] = (l == 0) ? 0 : s[l];
  51.  
  52.             while (l && h[s[l]] >= h[j]) // Continue Maintain stack
  53.                 --l;
  54.  
  55.             s[++l] = j;
  56.         }
  57.  
  58.         l = 0; // Reset Stack
  59.         for (int j = m; j; --j)
  60.         {
  61.             while (l && h[s[l]] >= oldh[j]) // Find Right Bound of Rectangle
  62.                 --l;
  63.  
  64.             R[j] = (l == 0) ? m + 1 : s[l];
  65.  
  66.             while (l && h[s[l]] >= h[j]) // Continue Maintain stack
  67.                 --l;
  68.  
  69.             s[++l] = j;
  70.         }
  71.  
  72.         for (int j = 1; j <= m; ++j)
  73.             if(oldh[j] > h[j]) // Những cột j không tồn tại last(i,j) thì không xét
  74.                 ans = max(ans, (R[j] - L[j] - 1) * oldh[j]);
  75.     }
  76.  
  77.     cout << ans;
  78. }
  79.  
  80. int32_t main()
  81. {
  82.     ios::sync_with_stdio(0);
  83.     cin.tie(0);
  84.     cout.tie(0);
  85.     Read();
  86.     Solve();
  87. }
  88.  
  89. /*
  90. Input:
  91. 4 5 4
  92. 2 3
  93. 2 5
  94. 3 1
  95. 4 4
  96.  
  97. Output:
  98. 9
  99. */
Advertisement
RAW Paste Data Copied
Advertisement