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