fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int findQudruplets(vector<int> &arr, int k1, int k2){
  5. 	int n = arr.size(), totalCnt = 0;
  6. 	if(n < 4){
  7. 		return 0;
  8. 	}
  9.  
  10. 	vector<int> s(n, 0);
  11.  
  12. 	for (int k = 2; k <= n-2; k++){
  13. 		int idx = upper_bound(arr.begin()+k+1, arr.end(), k2 - arr[k]) - arr.begin();
  14. 		s[k] = n-idx;
  15. 	}
  16.  
  17. 	vector<int> r(n+1, 0);
  18.  
  19. 	for(int k = n-2; k >= 2; k--){
  20. 		r[k] = r[k+1]+s[k]; 
  21. 	}
  22.  
  23. 	for (int j = 1; j <= n-3; j++){
  24.  
  25. 		int pos = upper_bound(arr.begin(), arr.begin()+j, k1 - arr[j]) - arr.begin();
  26. 		int leftCnt = (j - pos);
  27.  
  28. 		int rightCnt = r[j+1];
  29.  
  30. 		totalCnt += leftCnt * rightCnt;
  31.  
  32. 	}
  33.  
  34. 	return totalCnt;
  35. }
  36.  
  37.  
  38. int main() {
  39. 	// your code goes here
  40. 	vector<int> arr = {1, 1, 1, 1, 2, 2};
  41. 	cout << findQudruplets(arr, 1, 3);
  42.  
  43. 	return 0;
  44. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
6
https://ideone.com/sA0MnW
language:
C++14 (gcc 8.3)
created:
14 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!