Advertisement
Hezov

dreptunghi1

Oct 6th, 2024
39
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1. ///Usor (bine mediu..)
  2. #include <fstream>
  3. #include <algorithm>
  4. using namespace std;
  5. ifstream cin("dreptunghi1.in");
  6. ofstream cout("dreptunghi1.out");
  7. const int mxN = 1e4;
  8. pair<int,int> p[mxN+2];
  9. int st[mxN+1],l[mxN+1],r[mxN+1],v[mxN+1];
  10. int skyline(int v[], int n)
  11. {
  12.     int top = 0, sol = 0;
  13.     for(int i = 1;i<=n;i++)
  14.         l[i] = r[i] = 0;
  15.     for(int i = 1;i<=n;i++)
  16.     {
  17.         while(top > 0 && v[st[top]] > v[i])
  18.             r[st[top]] = i , top--;
  19.         st[++top] = i;
  20.     }
  21.     while(top>0) r[st[top]] = n+1, top--;
  22.     for(int i = n;i>0;i--)
  23.     {
  24.         while(top > 0 && v[st[top]] > v[i])
  25.             l[st[top]] = i, top--;
  26.         st[++top] = i;
  27.     }
  28.     for(int i = 1;i<=n;i++)
  29.     {
  30.        int res = v[i] * (r[i] - l[i] - 1);
  31.        sol = max(sol,res);
  32.     }
  33.     return sol;
  34. }
  35. int main()
  36. {
  37.     int n , m , z;
  38.     cin>>n>>m>>z;
  39.     for(int i = 1;i<=z;i++)
  40.         cin>>p[i].first>>p[i].second;
  41.     sort(p+1,p+1+z);
  42.     p[z+1].first = p[z+1].second = 1e9;
  43.     int k = 1, sol = 0;
  44.     for(int i = 1;i<=n;i++)
  45.     {
  46.         for(int j = 1;j<=m;j++)
  47.         {
  48.             if(i >= p[k].first)
  49.             {
  50.                 while(i>p[k].first) k++;
  51.  
  52.                 while(j > p[k].second && p[k].first <= i) k++;
  53.             }
  54.  
  55.             if(i==p[k].first&&j==p[k].second) v[j] = 0;
  56.             else v[j]++;
  57.         }
  58.         sol = max(sol,skyline(v,m));
  59.     }
  60.     cout<<sol<<'\n';
  61.     return 0;
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement