paradox64ce

TheWireUs-Day3

Sep 20th, 2020
823
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4.  
  5. using namespace std;
  6.  
  7. int main()
  8. {
  9.     ll n, ans = -1e18;
  10.     cin >> n;
  11.     vector<pair<ll, ll>> v(n);
  12.     for (ll i = 0; i < n; i++)
  13.     {
  14.         cin >> v[i].first;
  15.         v[i].second = i + 1;
  16.     }
  17.     stack<pair<ll, ll>> S1, S2;
  18.     vector<ll> a, b;
  19.  
  20.     for (ll i = 0; i < n; i++)
  21.     {
  22.         while (!S1.empty() && S1.top().first >= v[i].first)
  23.         {
  24.             S1.pop();
  25.         }
  26.         if (S1.empty())
  27.         {
  28.             a.push_back(0);
  29.         }
  30.         else
  31.         {
  32.             a.push_back(S1.top().second);
  33.         }
  34.         S1.push(v[i]);
  35.     }
  36.  
  37.     for (ll i = n - 1; i >= 0; --i)
  38.     {
  39.         while (!S2.empty() && S2.top().first >= v[i].first)
  40.         {
  41.             S2.pop();
  42.         }
  43.         if (S2.empty())
  44.         {
  45.             b.push_back(n + 1);
  46.         }
  47.         else
  48.         {
  49.             b.push_back(S2.top().second);
  50.         }
  51.         S2.push(v[i]);
  52.     }
  53.    
  54.     reverse(b.begin(), b.end());
  55.    
  56.     for (ll i = 0; i < n; i++)
  57.     {
  58.         ans = max(ans, v[i].first * (b[i] - a[i] - 1));
  59.     }
  60.     cout << ans << "\n";
  61.  
  62.     return 0;
  63. }
RAW Paste Data