Artifact 73000b9fbf0fd9f67f0e7ab4b5cbeb7e2b35b25a:
0000: 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d //--------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
0040: 2f 2f 20 68 5b 5d 20 3a 20 6c 69 73 74 20 6f 66 // h[] : list of
0050: 20 68 65 69 67 68 74 73 0a 2f 2f 20 20 20 69 2d heights.// i-
0060: 74 68 20 72 65 63 74 61 6e 67 6c 65 20 69 73 20 th rectangle is
0070: 6c 6f 63 61 74 65 64 20 61 74 20 28 69 2c 30 29 located at (i,0)
0080: 2d 2d 28 69 2b 31 2c 68 5b 69 5d 29 0a 2f 2f 0a --(i+1,h[i]).//.
0090: 2f 2f 20 63 61 6c 63 75 6c 61 74 65 20 74 68 65 // calculate the
00a0: 20 61 72 65 61 20 6f 66 20 6d 61 78 69 6d 75 6d area of maximum
00b0: 20 73 75 62 2d 72 65 63 74 61 6e 67 6c 65 0a 2f sub-rectangle./
00c0: 2f 0a 2f 2f 20 56 65 72 69 66 69 65 64 20 62 79 /.// Verified by
00d0: 0a 2f 2f 20 20 20 2d 20 53 52 4d 20 33 33 37 20 .// - SRM 337
00e0: 44 69 76 31 20 4c 56 32 0a 2f 2f 2d 2d 2d 2d 2d Div1 LV2.//-----
00f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0100: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0110: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0120: 2d 2d 2d 2d 2d 2d 2d 2d 0a 0a 09 09 2f 2f 20 73 --------....// s
0130: 6f 6c 76 65 0a 09 09 76 65 63 74 6f 72 3c 69 6e olve...vector<in
0140: 74 3e 20 6c 65 66 74 28 6e 29 3b 0a 09 09 7b 0a t> left(n);...{.
0150: 09 09 09 6d 61 70 3c 4c 4c 2c 20 69 6e 74 3e 20 ...map<LL, int>
0160: 68 3b 20 68 5b 2d 31 5d 20 3d 20 2d 31 3b 0a 09 h; h[-1] = -1;..
0170: 09 09 66 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 ..for(int i=0; i
0180: 3c 6e 3b 20 2b 2b 69 29 20 7b 0a 09 09 09 09 2f <n; ++i) {...../
0190: 2f 20 70 6f 73 69 74 69 6f 6e 20 6f 66 20 74 68 / position of th
01a0: 65 20 68 69 67 68 65 73 74 20 62 75 69 6c 64 69 e highest buildi
01b0: 6e 67 20 3c 20 52 5b 69 5d 0a 09 09 09 09 6d 61 ng < R[i].....ma
01c0: 70 3c 4c 4c 2c 69 6e 74 3e 3a 3a 69 74 65 72 61 p<LL,int>::itera
01d0: 74 6f 72 20 69 74 20 3d 20 68 2e 6c 6f 77 65 72 tor it = h.lower
01e0: 5f 62 6f 75 6e 64 28 52 5b 69 5d 29 3b 0a 09 09 _bound(R[i]);...
01f0: 09 09 6c 65 66 74 5b 69 5d 20 3d 20 28 2d 2d 69 ..left[i] = (--i
0200: 74 29 2d 3e 73 65 63 6f 6e 64 2b 31 3b 0a 09 09 t)->second+1;...
0210: 09 09 68 2e 65 72 61 73 65 28 20 2b 2b 69 74 2c ..h.erase( ++it,
0220: 20 68 2e 65 6e 64 28 29 20 29 3b 0a 09 09 09 09 h.end() );.....
0230: 68 5b 20 52 5b 69 5d 20 5d 20 3d 20 69 3b 0a 09 h[ R[i] ] = i;..
0240: 09 09 7d 0a 09 09 7d 0a 09 09 76 65 63 74 6f 72 ..}...}...vector
0250: 3c 69 6e 74 3e 20 72 69 67 68 74 28 6e 29 3b 0a <int> right(n);.
0260: 09 09 7b 0a 09 09 09 6d 61 70 3c 4c 4c 2c 20 69 ..{....map<LL, i
0270: 6e 74 3e 20 68 3b 20 68 5b 2d 31 5d 20 3d 20 6e nt> h; h[-1] = n
0280: 3b 0a 09 09 09 66 6f 72 28 69 6e 74 20 69 3d 6e ;....for(int i=n
0290: 2d 31 3b 20 69 3e 3d 30 3b 20 2d 2d 69 29 20 7b -1; i>=0; --i) {
02a0: 0a 09 09 09 09 2f 2f 20 70 6f 73 69 74 69 6f 6e .....// position
02b0: 20 6f 66 20 74 68 65 20 68 69 67 68 65 73 74 20 of the highest
02c0: 62 75 69 6c 64 69 6e 67 20 3c 20 52 5b 69 5d 0a building < R[i].
02d0: 09 09 09 09 6d 61 70 3c 4c 4c 2c 69 6e 74 3e 3a ....map<LL,int>:
02e0: 3a 69 74 65 72 61 74 6f 72 20 69 74 20 3d 20 68 :iterator it = h
02f0: 2e 6c 6f 77 65 72 5f 62 6f 75 6e 64 28 52 5b 69 .lower_bound(R[i
0300: 5d 29 3b 0a 09 09 09 09 72 69 67 68 74 5b 69 5d ]);.....right[i]
0310: 20 3d 20 28 2d 2d 69 74 29 2d 3e 73 65 63 6f 6e = (--it)->secon
0320: 64 2d 31 3b 0a 09 09 09 09 68 2e 65 72 61 73 65 d-1;.....h.erase
0330: 28 20 2b 2b 69 74 2c 20 68 2e 65 6e 64 28 29 20 ( ++it, h.end()
0340: 29 3b 0a 09 09 09 09 68 5b 20 52 5b 69 5d 20 5d );.....h[ R[i] ]
0350: 20 3d 20 69 3b 0a 09 09 09 7d 0a 09 09 7d 0a 09 = i;....}...}..
0360: 09 4c 4c 20 61 6e 73 20 3d 20 30 3b 0a 09 09 66 .LL ans = 0;...f
0370: 6f 72 28 69 6e 74 20 69 3d 30 3b 20 69 3c 6e 3b or(int i=0; i<n;
0380: 20 2b 2b 69 29 20 7b 0a 09 09 09 4c 4c 20 61 72 ++i) {....LL ar
0390: 65 61 20 3d 20 52 5b 69 5d 20 2a 20 28 72 69 67 ea = R[i] * (rig
03a0: 68 74 5b 69 5d 20 2d 20 6c 65 66 74 5b 69 5d 20 ht[i] - left[i]
03b0: 2b 20 31 29 3b 0a 09 09 09 61 6e 73 20 3d 20 6d + 1);....ans = m
03c0: 61 78 28 61 6e 73 2c 20 61 72 65 61 29 3b 0a 09 ax(ans, area);..
03d0: 09 7d 0a 09 09 72 65 74 75 72 6e 20 61 6e 73 3b .}...return ans;
03e0: 0a .