fork download
  1. import java.util.Scanner;
  2. class SubarrayCount {
  3. public static void main(String[] args) {
  4. Scanner scanner = new Scanner(System.in);
  5.  
  6. long n = scanner.nextLong();
  7. long k = scanner.nextLong();
  8. long[] b = new long[(int)n];
  9.  
  10. for (int i = 0; i < n; i++) {
  11. b[i] = scanner.nextLong();
  12. }
  13.  
  14. long count = 0, sum = 0;
  15. int j = 0;
  16.  
  17. for (int i = 0; i < n; i++) {
  18. // what if the entire arr has sum <k then j might increment infinitely or ot of bounds so j<n
  19. // move j so than sum is greater .. i.. j is valid .. then we need to find next i from which sum is valid.
  20. // shrink window by removing b[i] at end
  21. while (j < n && sum < k) {
  22. sum += b[j];
  23. j++;
  24. }
  25. // if sum >= k, then all subarrays starting at i and ending from j-1 .. n-1 are valid
  26. if (sum >= k) {
  27. count += (n - j + 1);
  28. }
  29.  
  30. sum -= b[i]; // move i forward (shrink window)
  31. }
  32.  
  33. System.out.println(count);
  34. scanner.close();
  35. }
  36. }
  37.  
Success #stdin #stdout 0.17s 56512KB
stdin
15 10 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
stdout
105