Advertisement
Guest User

Untitled

a guest
Jul 17th, 2019
62
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.14 KB | None | 0 0
  1. import math
  2. import os
  3. import random
  4. import re
  5. import sys
  6. import bisect
  7.  
  8. # Complete the activityNotifications function below.
  9. def activityNotifications(expenditure, d):
  10. temp = []
  11. temp.extend(expenditure[0:d])
  12. # Must be initially sorted once
  13. temp.sort()
  14. #print(len(temp), len(expenditure[:d]), d, len(expenditure))
  15. mid, mid1 = None, None
  16. mid = d // 2
  17. #print(d, temp, mid, len(temp))
  18. med = temp[mid]
  19. if d % 2 == 0:
  20. mid1 = mid-1
  21. med += temp[mid]
  22. med /= 2
  23. cnt = 0
  24. for i in range(d, len(expenditure)):
  25. #print(temp, d, expenditure[i])
  26. if expenditure[i] >= 2*med:
  27. cnt += 1
  28. idx = bisect.bisect(temp, expenditure[i-d])
  29. #print(idx)
  30. del temp[idx]
  31. bisect.insort(temp, expenditure[i])
  32. med = temp[mid]
  33. if mid1 != None:
  34. med += temp[mid1]
  35. med /= 2
  36.  
  37. return cnt
  38.  
  39.  
  40. if __name__ == '__main__':
  41. nd = input().split()
  42.  
  43. n = int(nd[0])
  44.  
  45. d = int(nd[1])
  46.  
  47. expenditure = list(map(int, input().rstrip().split()))
  48.  
  49. result = activityNotifications(expenditure, d)
  50.  
  51. print(str(result) + 'n')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement