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