Advertisement
EternalBliss69

Untitled

Sep 24th, 2022
994
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.83 KB | None | 0 0
  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