fork download 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAXN = 5005;
  6.  
  7. struct rect
  8. {
  9.     int x1, y1, x2, y2, c;
  10. };
  11.  
  12. rect r[MAXN];
  13. rect cr[MAXN];
  14. int x[MAXN], y[MAXN];
  15. bool grid[MAXN][MAXN];
  16. int h[MAXN];
  17. int l[MAXN], st[MAXN];
  18. int n;
  19.  
  20. long long solve(int num)
  21. {
  22.     if (num == 0) return 0;
  23.  
  24.     int xc = 0, yc = 0;
  25.     for (int i = 0; i < num; ++i)
  26.     {
  27.         x[xc++] = cr[i].x1;
  28.         x[xc++] = cr[i].x2;
  29.         y[yc++] = cr[i].y1;
  30.         y[yc++] = cr[i].y2;
  31.     }
  32.  
  33.     sort(x, x + xc);
  34.     sort(y, y + yc);
  35.     xc = unique(x, x + xc) - x;
  36.     yc = unique(y, y + yc) - y;
  37.  
  38.     for (int i = 0; i < yc; ++i)
  39.     {
  40.         for (int j = 0; j < xc; ++j)
  41.         {
  42.             grid[i][j] = false;
  43.         }
  44.     }
  45.  
  46.     for (int i = 0; i < num; ++i)
  47.     {
  48.         int x1i = lower_bound(x, x + xc, cr[i].x1) - x;
  49.         int x2i = lower_bound(x, x + xc, cr[i].x2) - x;
  50.         int y1i = lower_bound(y, y + yc, cr[i].y1) - y;
  51.         int y2i = lower_bound(y, y + yc, cr[i].y2) - y;
  52.  
  53.         for (int row = y1i; row < y2i; ++row)
  54.         {
  55.             for (int col = x1i; col < x2i; ++col)
  56.             {
  57.                 grid[row][col] = true;
  58.             }
  59.         }
  60.     }
  61.  
  62.     long long maxarea = 0;
  63.     for (int j = 0; j < xc; ++j) h[j] = 0;
  64.  
  65.     for (int i = 0; i < yc - 1; ++i)
  66.     {
  67.         for (int j = 0; j < xc - 1; ++j)
  68.         {
  69.             if (grid[i][j])
  70.             {
  71.                 h[j]++;
  72.             }
  73.             else
  74.             {
  75.                 h[j] = 0;
  76.             }
  77.         }
  78.  
  79.         int top = 0;
  80.         for (int j = 0; j < xc - 1; ++j)
  81.         {
  82.             while (top > 0 && h[st[top - 1]] >= h[j])
  83.             {
  84.                 top--;
  85.             }
  86.             l[j] = (top == 0) ? -1 : st[top - 1];
  87.             st[top++] = j;
  88.         }
  89.  
  90.         top = 0;
  91.         for (int j = xc - 2; j >= 0; --j)
  92.         {
  93.             while (top > 0 && h[st[top - 1]] >= h[j])
  94.             {
  95.                 top--;
  96.             }
  97.             int right = (top == 0) ? xc - 1 : st[top - 1];
  98.             if(h[j] > 0)
  99.             {
  100.                 maxarea = max(maxarea, 1LL * (y[i + 1] - y[i - h[j] + 1]) * (x[right] - x[l[j] + 1]));
  101.             }
  102.             st[top++] = j;
  103.         }
  104.     }
  105.     return maxarea;
  106. }
  107.  
  108. int main()
  109. {
  110.     ios_base::sync_with_stdio(0);
  111.     cin.tie(0);
  112.     cout.tie(0);
  113.     if (fopen("d5msrect.inp", "r"))
  114.     {
  115.         freopen("d5msrect.inp", "r", stdin);
  116.         freopen("d5msrect.out", "w", stdout);
  117.     }
  118.     cin >> n;
  119.  
  120.     for (int i = 0; i < n; ++i)
  121.     {
  122.         cin >> r[i].x1 >> r[i].y1 >> r[i].x2 >> r[i].y2 >> r[i].c;
  123.     }
  124.  
  125.     long long ans = 0;
  126.  
  127.     sort(r, r + n, [](const rect& a, const rect& b)
  128.     {
  129.         return a.c < b.c;
  130.     });
  131.  
  132.     int start = 0;
  133.     for (int i = 0; i < n; ++i)
  134.     {
  135.         if (i > 0 && r[i].c != r[i - 1].c)
  136.         {
  137.             int num = 0;
  138.             for (int j = start; j < i; ++j)
  139.             {
  140.                 cr[num++] = r[j];
  141.             }
  142.             ans = max(ans, solve(num));
  143.             start = i;
  144.         }
  145.     }
  146.  
  147.     int num = 0;
  148.     for (int j = start; j < n; ++j)
  149.     {
  150.         cr[num++] = r[j];
  151.     }
  152.     ans = max(ans, solve(num));
  153.  
  154.     cout << ans << endl;
  155.  
  156.     return 0;
  157. }
  158.  
Success #stdin #stdout 0s 5332KB
comments (?)
stdin 
Standard input is empty
stdout 
0
https://ideone.com/pdHBgp
language:
C++14 (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!