Advertisement

# Untitled

Sep 24th, 2022
994
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. n = int(input())
2. heights = []
3. previous_point1 = None
4. previous_point2 = None
5. for i in range(n):
6.     point = input().split(" ")
7.     if previous_point1 is None:
8.         previous_point1 = point
9.     elif previous_point2 is None:
10.         previous_point2 = point
11.     else:
12.         height = int(point[1])
13.         width = int(point[0]) - int(previous_point1[0])
14.         while width > 0:
15.             heights.append(height)
16.             width -= 1
17.         previous_point1 = point
18.         previous_point2 = None
19.
20.
21. def nsl(heights):
22.     stack = []
23.     ans = []
24.     for i in range(len(heights)):
25.         if len(stack) == 0:
26.             ans.append(-1)
27.         elif len(stack) > 0 and heights[i] >= heights[stack[-1]]:
28.             ans.append(stack[-1])
29.         elif len(stack) > 0 and heights[i] < heights[stack[-1]]:
30.             while len(stack) > 0 and heights[i] < heights[stack[-1]]:
31.                 stack.pop()
32.             if len(stack) == 0:
33.                 ans.append(-1)
34.             else:
35.                 ans.append(stack[-1])
36.         stack.append(i)
37.     return ans
38.
39.
40. def nsr(heights):
41.     stack = []
42.     ans = []
43.     for i in reversed(range(len(heights))):
44.         if len(stack) == 0:
45.             ans.append(len(heights))
46.         elif len(stack) > 0 and heights[i] > heights[stack[-1]]:
47.             ans.append(stack[-1])
48.         elif len(stack) > 0 and heights[i] <= heights[stack[-1]]:
49.             while len(stack) > 0 and heights[i] <= heights[stack[-1]]:
50.                 stack.pop()
51.             if len(stack) == 0:
52.                 ans.append(len(heights))
53.             else:
54.                 ans.append(stack[-1])
55.         stack.append(i)
56.     return ans[::-1]
57.
58.
59. nsla = nsl(heights)
60. nsra = nsr(heights)
61.
62. maxa = 0
63.
64. for i in range(len(heights)):
65.     maxa = max(maxa, (nsra[i] - nsla[i] - 1) * heights[i])
66.
67. print(maxa)
68.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement