fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3. typedef long long ll;
  4.  
  5. int main() {
  6. 	int n;
  7. 	cin >> n;
  8.  
  9. 	int arr[n+1];
  10.  
  11. 	for(int i=0; i<n; i++) {
  12. 		cin >> arr[i];
  13. 	}
  14.  
  15. 	int k1, k2;
  16. 	cin >> k1 >> k2;
  17.  
  18. 	ll ans = 0;
  19.  
  20. 	for(int j=1; j<=n-3; j++) {
  21. 		int leftPairs = 0;
  22.  
  23. 	    // Count valid (i, j)
  24. 		for(int i=0; i<j; i++) {
  25. 			if(arr[i] + arr[j] > k1) {
  26. 				leftPairs++;
  27. 			}
  28. 		}
  29.  
  30. 		// Count valid (k, l), where k > j
  31.         long long rightPairs = 0;
  32.         int k = j + 1;
  33.         int l = n - 1;
  34.  
  35.         while(k < l) {
  36.         	if (arr[k] + arr[l] > k2) {
  37. 	            // Since array is sorted,
  38. 	            // (k, l), (k+1, l), ..., (l-1, l) are all valid
  39. 	            rightPairs += (l - k);
  40. 	            l--;
  41.             } else {
  42.                 k++;
  43.             }
  44.         }
  45.  
  46. 		ans += leftPairs * rightPairs;
  47. 	}
  48.  
  49. 	cout << " Count of Quadruplets: " << ans;
  50. 	return 0;
  51. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
5
1
2
3
4
5
2
4
stdout
copy 
 Count of Quadruplets: 5
https://ideone.com/nx2oAA
language:
C++ (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!