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. # We use j and k as the two inner pointers
  10. for j in range(1, n - 2):
  11. for k in range(j + 1, n - 1):
  12.  
  13. # Pointer i: find the first index where a[i] + a[j] > k1
  14. # We can use a 3rd pointer starting from 0 up to j-1
  15. i = 0
  16. while i < j and a[i] + a[j] <= k1:
  17. i += 1
  18. valid_i_count = j - i # All elements from i to j-1 are valid
  19.  
  20. # Pointer l: find the first index from the right where a[k] + a[l] <= k2
  21. # Our 4th pointer 'l' counts how many elements from the end satisfy the condition
  22. l = n - 1
  23. while l > k and a[k] + a[l] > k2:
  24. l -= 1
  25. valid_l_count = n - 1 - l # All elements from l+1 to n-1 are valid
  26.  
  27. total_quadruplets += valid_i_count * valid_l_count
  28.  
  29. return total_quadruplets
  30.  
Success #stdin #stdout 0.08s 14148KB
stdin
Standard input is empty
stdout
Standard output is empty