Artifact Content
Not logged in

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;