SHARE
TWEET

hambar(#1972) Stiva

UnknownPrecentage Jun 12th, 2019 (edited) 58 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. ifstream f("hambar.in");
  4. ofstream g("hambar.out");
  5. struct ab{int i, j;};
  6. ab a[1001];
  7. int v[1001];
  8. int n, m, i, j, k, mx;
  9. void quicksort(int st, int dr)
  10. {
  11.     if(st < dr)
  12.     {
  13.         int mij = (st + dr) / 2;
  14.         swap(a[mij], a[st]);
  15.         int i = st, j = dr, d = 0;
  16.         while(i < j)
  17.         {
  18.             if(a[i].i > a[j].i) swap(a[i], a[j]), d = 1 - d;
  19.             else if(a[i].i == a[j].i && a[i].j > a[j].j) swap(a[i], a[j]), d = 1 - d;
  20.             i += d;
  21.             j -= (1 - d);
  22.         }
  23.         quicksort(st, i - 1);
  24.         quicksort(i + 1, dr);
  25.     }
  26. }
  27. int mxA(int a[])
  28. {
  29.     int st[1001];
  30.     int mxArea = 0, A;
  31.     int k = 0, i;
  32.     st[++k] = 0;
  33.     for(i = 1;i <= n + 1;i++)
  34.     {
  35.         while(k && (a[st[k]] > a[i]))
  36.         {
  37.             k--;
  38.             if(k) A = a[st[k + 1]] * (i - st[k] - 1);
  39.             else A = a[st[k + 1]] * i;
  40.             mxArea = max(mxArea, A);
  41.         }
  42.         st[++k] = i;
  43.     }
  44.     return mxArea;
  45. }
  46. int main()
  47. {
  48.     f >> n >> m;
  49.     for(i = 1;i <= m;i++) f >> a[i].i >> a[i].j;
  50.     quicksort(1, m), k = 1;
  51.     for(i = 1;i <= n;i++)
  52.     {
  53.         for(j = 1;j <= n;j++)
  54.             if(a[k].i == i && a[k].j == j)
  55.             {
  56.                 v[j] = 0;
  57.                 while(k <= m && a[k].i == i && a[k].j == j) k++;
  58.             }
  59.             else v[j]++;
  60.         mx = max(mx, mxA(v));
  61.     }
  62.     g << mx;
  63. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top