DeepRest

Number of Subarrays with bounded maximum

Jun 18th, 2021 (edited)
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.41 KB | None | 0 0
  1. #python 3.7.1
  2.  
  3. left, right = map(int, input().split())
  4. nums = [int(i) for i in input().split()]
  5.  
  6. partitions = []
  7. p = []
  8. for i in nums:
  9. if i > right:
  10. partitions.append(p)
  11. p = []
  12. else:
  13. p.append(i)
  14. partitions.append(p)
  15.  
  16. ans = 0
  17. for p in partitions:
  18. start = 0
  19. end = len(p)
  20. for i, e in enumerate(p):
  21. if e >= left:
  22. ans += (i-start+1) * (end-i)
  23. start = i+1
  24.  
  25. print(ans)
Add Comment
Please, Sign In to add comment