# Histogram

Feb 22nd, 2024
963
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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. }