fork download
  1. def count_quadruplets_ordered_4_pointers(a: list[int], k1: int, k2: int) -> int:
  2. """
  3. Counts quadruplets (i, j, k, l) with i < j < k < l
  4. such that a[i] + a[j] > k1 and a[k] + a[l] > k2.
  5. """
  6. n = len(a)
  7. total_quadruplets = 0
  8.  
  9.  
  10. for j in range(1, n - 2):
  11. for k in range(j + 1, n - 1):
  12.  
  13.  
  14. i = 0
  15. while i < j and a[i] + a[j] <= k1:
  16. i += 1
  17. valid_i_count = j - i
  18.  
  19.  
  20. l = n - 1
  21. while l > k and a[k] + a[l] > k2:
  22. l -= 1
  23. valid_l_count = n - 1 - l
  24.  
  25. total_quadruplets += valid_i_count * valid_l_count
  26.  
  27. return total_quadruplets
  28.  
Success #stdin #stdout 0.07s 14024KB
stdin
Standard input is empty
stdout
Standard output is empty