Advertisement
Guest User

Untitled

a guest
Jan 23rd, 2018
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.78 KB | None | 0 0
  1. def get_prefix(l, r):
  2. return prefix[r] - prefix[l - 1] if l else prefix[r]
  3.  
  4.  
  5. n, k = map(int, input().split())
  6. arr = list(map(int, input().split()))
  7. arr.sort()
  8. arr1 = []
  9. cnt = 1
  10. for i in range(1, n):
  11. if arr[i - 1] != arr[i]:
  12. arr1.append((arr[i - 1], cnt))
  13. cnt = 1
  14. else:
  15. cnt += 1
  16. arr1.append((arr[i - 1], cnt))
  17. arr1.sort()
  18. pnt = 0
  19. n = len(arr1)
  20. ans = 0
  21. for i in range(n):
  22. arr1[i] = (arr1[i][0], arr1[i][1], int(arr1[i][1] >= 2))
  23. if arr1[i] >= 3:
  24. ans += 1
  25. prefix = [0] * n
  26. for i in range(n):
  27. prefix[i] = arr1[i][1] + prefix[i - 1]
  28. for i in range(n):
  29. while pnt < n - 1 and arr1[pnt + 1][0] <= arr1[i][0] * k:
  30. pnt += 1
  31. ans += (i - pnt) * (i - pnt - 1) // 2 + get_prefix(i, pnt)
  32. print(ans, prefix, arr1)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement