Advertisement
wrench786

Histogram

Feb 22nd, 2024
963
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.07 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. typedef unsigned long long ull;
  6. #define nn "\n"
  7. #define mod 1000000007
  8.  
  9. const ll mx = 3e4+7;
  10.  
  11. ll tree[mx*4];
  12. ll arr[mx];
  13.  
  14. ll merge(ll left, ll right){
  15.     return min(left,right);
  16. }
  17.  
  18. void tree_build(ll node, ll ls, ll rs){
  19.     if(ls==rs){
  20.         tree[node] = arr[ls];
  21.         return;
  22.     }
  23.     ll left = node*2;
  24.     ll right = node*2+1;
  25.     ll mid = (ls+rs)/2;
  26.  
  27.     tree_build(left,ls,mid);
  28.     tree_build(right,mid+1,rs);
  29.    
  30.     tree[node] = merge(tree[left],tree[right]); // change
  31. }
  32.  
  33. ll tree_query(ll node, ll ls, ll rs, ll x, ll y){
  34.     if(ls>y || rs<x) return mx; //change
  35.     if(ls>=x && rs<=y) return tree[node];
  36.    
  37.     ll left = node*2;
  38.     ll right = node*2+1;
  39.     ll mid = (ls+rs)/2;
  40.  
  41.     ll res1 = tree_query(left,ls, mid, x, y);
  42.     ll res2 = tree_query(right, mid+1, rs, x, y);
  43.    
  44.     return merge(res1,res2); //change
  45. }
  46.  
  47. // check ll overflow
  48. void solve(){
  49.     ll n;
  50.     cin>>n;
  51.  
  52.     for(ll i=1;i<=n;i++) cin>>arr[i];
  53.  
  54.     tree_build(1,1,n);
  55.  
  56.     ll result = 0;
  57.     for(ll i=1;i<=n;i++){
  58.         ll x = arr[i];
  59.  
  60.         ll l = 1, r = i-1, m, lans=0,rans=0;
  61.         while(l<=r){
  62.             m = (l+r)/2;
  63.            
  64.             if(tree_query(1,1,n,m,i)==x){
  65.                 lans = max(lans, i-m);
  66.                 r = m-1;
  67.             }
  68.             else l = m+1;
  69.         }
  70.         l = i+1,r = n;
  71.         while(l<=r){
  72.             m = (l+r)/2;
  73.  
  74.             if(tree_query(1,1,n,i,m)==x){
  75.                 rans = max(rans, m-i);
  76.                 l = m+1;
  77.             }
  78.             else r = m-1;
  79.         }
  80.         //if(arr[i]==2) cout<<lans<<" "<<rans<<nn;
  81.         result = max(result, 1ll*(lans+1+rans)*arr[i]);
  82.     }
  83.     cout<<result<<nn;
  84. }  
  85.  
  86. int main()
  87. {
  88.     ios_base::sync_with_stdio(0);
  89.     cin.tie(0);
  90.  
  91.     // freopen("reduce.in", "r", stdin);
  92.     // freopen("reduce.out", "w", stdout);
  93.     int tc=1;
  94.     cin>>tc;
  95.    
  96.     int cases=0;
  97.     while(tc--){
  98.         cout<<"Case "<<++cases<<": ";
  99.         solve();
  100.     }
  101.     return 0;
  102. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement