fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long int ll;
  5. #define IOS ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
  6.  
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. using namespace __gnu_pbds;
  10.  
  11. typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>order_set;
  12. typedef pair<int, int>pr;
  13. #define all(i)     i.begin() , i.end()
  14. #define ft     first
  15. #define sn     second
  16. #define pb push_back
  17.  
  18. #define totalone(mask) __builtin_popcount(mask)
  19. #define chkbit(mask,bit) (mask&(1LL << bit))
  20. #define setbit(mask,bit) (mask|(1LL << bit))
  21. #define cngbit(mask,bit) (mask^(1LL << bit))
  22.  
  23. #define en "\n"
  24. #define dbg(x) cerr<<#x<<" is : "<<x<<en;
  25. #define here cout<<"rony\n"
  26. #define yes cout<<"YES\n";
  27. #define no cout<<"NO\n";
  28. #define report cout<<-1<<en;
  29. #define sum(n) ((1LL*(n)*(n+1))/ 2LL)
  30. #define sqr(n) (1LL*(n)*(n))
  31. #define vag(a,b) ((a + b - 1)/b)
  32. #define coutv(v) for(auto i: v) cout<<i<<" ";cout<<en;
  33. #define cinv(v) for(auto &i: v) cin >> i;
  34.  
  35. #define MAXN 100001
  36. #define inf 1e6+5
  37. const int mod = 1e9 + 7;
  38.  
  39. vector<int>g[MAXN];
  40. int vis[MAXN];
  41. ll a[MAXN];
  42.  
  43. struct segment_tree
  44. {
  45.     struct node {
  46.         int suru , ses, value;
  47.  
  48.         void init(int l, int r) {
  49.             suru = l, ses = r;
  50.             if (l == r) value = a[l];
  51.         }
  52.     } g[4 * MAXN];
  53.  
  54.     void fill_cn(node &cn, node &ln, node &rn) // fill_current_node
  55.     {
  56.         cn.value = min(ln.value, rn.value);
  57.     }
  58.  
  59.     void build(int cn, int l, int r)
  60.     {
  61.         g[cn].init(l, r);
  62.  
  63.         if (l == r ) return;
  64.         int md = l + (r - l) / 2;
  65.  
  66.         build(cn * 2, l, md);
  67.         build(cn * 2 + 1, md + 1, r);
  68.  
  69.         fill_cn (g[cn], g[cn * 2] , g[cn * 2 + 1]);
  70.     }
  71.  
  72.     void update(int cn, int pos, int val)
  73.     {
  74.         int x = g[cn].suru;
  75.         int y = g[cn].ses;
  76.  
  77.         if (y < pos || x > pos) return;
  78.         if (pos <= x && pos >= y ) {
  79.             g[cn].value = val;
  80.             return;
  81.         }
  82.  
  83.         update(cn * 2, pos, val);
  84.         update(cn * 2 + 1, pos, val);
  85.  
  86.         fill_cn(g[cn], g[cn * 2], g[cn * 2 + 1]);
  87.     }
  88.  
  89.     int query(int cn, int l, int r)
  90.     {
  91.         int x = g[cn].suru;
  92.         int y = g[cn].ses;
  93.         if (y < l || x > r) return INT_MAX;
  94.  
  95.         if (l <= x && r >= y ) return g[cn].value;
  96.  
  97.         int ans = query(cn * 2, l, r);
  98.         ans = min(ans, query(cn * 2 + 1, l, r));
  99.         return ans;
  100.     }
  101.  
  102. } stre;
  103.  
  104. int rightside(int l, int r, int k)
  105. {
  106.     int an = k;
  107.     while (l <= r)
  108.     {
  109.         int md = l + (r - l) / 2;
  110.         int mn = stre.query(1, l, md);
  111.         if (mn >= a[k]) {
  112.             an = md;
  113.             l = md + 1;
  114.         }
  115.         else r = md - 1;
  116.     }
  117.     return an;
  118. }
  119. int leftside(int l, int r, int k)
  120. {
  121.     int an = k;
  122.     while (l <= r)
  123.     {
  124.         int md = l + (r - l) / 2;
  125.         int mn = stre.query(1, md, r);
  126.         if (mn >= a[k]) {
  127.             an = md;
  128.             r = md - 1;
  129.         }
  130.         else l = md + 1;
  131.     }
  132.     return an;
  133. }
  134. void solve()
  135. {
  136.     int n;
  137.     cin >> n;
  138.  
  139.     for (int i = 1; i <= n; i++) {
  140.         cin >> a[i];
  141.     }
  142.  
  143.     stre.build(1, 1, n);
  144.     ll an = 0;
  145.  
  146.     for (int i = 1; i <= n; i++)
  147.     {
  148.         int l = leftside(1, i - 1, i);
  149.         int r = rightside(i + 1, n, i);
  150.         an = max(an, 1LL * a[i] * (r - l + 1));
  151.         // cout << l << " " << r << en;
  152.     }
  153.     cout << an << en;
  154. }
  155. int main()
  156. {
  157.     IOS;
  158.     ll t;
  159.     t = 1;
  160.     cin >> t;
  161.     int c = 0;
  162.     while ( t-- )
  163.     {
  164.         cout << "Case " << ++c << ": ";
  165.         solve();
  166.     }
  167.     return 0;
  168. }
Runtime error #stdin #stdout 0.01s 9772KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/Vz3VZe
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!