Advertisement
Dang_Quan_10_Tin

HCN HSGHN L9 2021-2022 (Compress Table Imple)

Aug 7th, 2022
909
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.55 KB | None | 0 0
  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. int x[N], y[N];    // List of position of character 'X'
  12.  
  13. int id[N]; // Real number of this column in the table
  14. int sz;    // Number of column contain at least 1 character 'X'
  15.  
  16. void Read()
  17. {
  18.     cin >> n >> m >> k;
  19.  
  20.     for (int i = 1; i <= k; ++i)
  21.     {
  22.         cin >> x[i] >> y[i];
  23.  
  24.         id[++sz] = y[i]; // Column y has at least 1 character 'X'
  25.     }
  26. }
  27.  
  28. void Solve()
  29. {
  30.     /* Change the table into new table that every column contain character 'X' */
  31.     sort(id + 1, id + sz + 1);
  32.     sz = unique(id + 1, id + sz + 1) - id - 1; // Remove duplicated column
  33.  
  34.     id[0] = 0;          // id_0 = 0
  35.     id[sz + 1] = m + 1; // id_back = m + 1
  36.  
  37.     for (int i = 1; i <= k; ++i)
  38.         X[x[i]].emplace_back(lower_bound(id + 1, id + sz + 1, y[i]) - id);
  39.  
  40.     /* Find the rectangle with maximum area */
  41.  
  42.     int ans(0);
  43.  
  44.     for (int i = 1; i <= n; ++i)
  45.     {
  46.         for (int j = 1; j <= sz; ++j)
  47.         {
  48.             // Update h_j, oldh_j = h'_j
  49.             ++h[j];
  50.             ++oldh[j];
  51.         }
  52.  
  53.         for (auto j : X[i])
  54.         {
  55.             oldh[j] = h[j]; // consider last(i,j) = 1
  56.             h[j] = 0;       // last(i, j) = (i, j)
  57.         }
  58.  
  59.         l = 0; // Reset Stack
  60.         for (int j = 1; j <= sz; ++j)
  61.         {
  62.             while (l && h[s[l]] >= oldh[j]) // Find Left Bound of Rectangle
  63.                 --l;
  64.  
  65.             L[j] = (l == 0) ? 0 : s[l];
  66.  
  67.             while (l && h[s[l]] >= h[j]) // Continue Maintain stack
  68.                 --l;
  69.  
  70.             s[++l] = j;
  71.         }
  72.  
  73.         l = 0; // Reset Stack
  74.         for (int j = sz; j; --j)
  75.         {
  76.             while (l && h[s[l]] >= oldh[j]) // Find Right Bound of Rectangle
  77.                 --l;
  78.  
  79.             R[j] = (l == 0) ? sz + 1 : s[l];
  80.  
  81.             while (l && h[s[l]] >= h[j]) // Continue Maintain stack
  82.                 --l;
  83.  
  84.             s[++l] = j;
  85.         }
  86.  
  87.         for (int j = 1; j <= sz; ++j)
  88.             if (oldh[j] > h[j]) // Những cột j không tồn tại last(i,j) thì không xét
  89.                 ans = max(ans, (id[R[j]] - id[L[j]] - 1) * oldh[j]);
  90.     }
  91.  
  92.     cout << ans;
  93. }
  94.  
  95. int32_t main()
  96. {
  97.     ios::sync_with_stdio(0);
  98.     cin.tie(0);
  99.     cout.tie(0);
  100.     Read();
  101.     Solve();
  102. }
  103.  
  104. /*
  105. Input:
  106. 4 5 4
  107. 2 3
  108. 2 5
  109. 3 1
  110. 4 4
  111.  
  112. Output:
  113. 9
  114. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement