Artifact 73000b9fbf0fd9f67f0e7ab4b5cbeb7e2b35b25a
//-------------------------------------------------------------
// h[] : list of heights
// i-th rectangle is located at (i,0)--(i+1,h[i])
//
// calculate the area of maximum sub-rectangle
//
// Verified by
// - SRM 337 Div1 LV2
//-------------------------------------------------------------
// solve
vector<int> left(n);
{
map<LL, int> h; h[-1] = -1;
for(int i=0; i<n; ++i) {
// position of the highest building < R[i]
map<LL,int>::iterator it = h.lower_bound(R[i]);
left[i] = (--it)->second+1;
h.erase( ++it, h.end() );
h[ R[i] ] = i;
}
}
vector<int> right(n);
{
map<LL, int> h; h[-1] = n;
for(int i=n-1; i>=0; --i) {
// position of the highest building < R[i]
map<LL,int>::iterator it = h.lower_bound(R[i]);
right[i] = (--it)->second-1;
h.erase( ++it, h.end() );
h[ R[i] ] = i;
}
}
LL ans = 0;
for(int i=0; i<n; ++i) {
LL area = R[i] * (right[i] - left[i] + 1);
ans = max(ans, area);
}
return ans;