fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6.  
  7.  
  8. const int M = 1000000007;
  9. const int N = 3e5+9;
  10. const int INF = 2e9+1;
  11. const int LINF = 2000000000000000001;
  12.  
  13. inline int power(int a, int b, int mod=M) {
  14.     int x = 1;
  15.     a %= mod;
  16.     while (b) {
  17.         if (b & 1) x = (x * a) % mod; 
  18.         a = (a * a) % mod;
  19.         b >>= 1;
  20.     }
  21.     return x;
  22. }
  23.  
  24.  
  25. //_ ***************************** START Below *******************************
  26.  
  27.  
  28.  
  29. vector<int> a;
  30.  
  31.  
  32. int bruteforce(int n, int k1, int k2){
  33. 	int ans = 0;
  34.  
  35. 	for(int i=0; i<n-2; i++){
  36. 		for(int j=i+1; j<n-2; j++){
  37. 			int leftSum = a[i] + a[j];
  38. 			if(leftSum <= k1) continue;
  39.  
  40. 			for(int k=j+1; k<n-1; k++){
  41. 				for(int l=k+1; l<n; l++){
  42. 					int rightSum = a[k] + a[l];
  43. 					if(rightSum > k2 ) ans++;
  44. 				}
  45. 			}
  46. 		}
  47. 	}
  48. 	return ans;
  49. }
  50.  
  51.  
  52.  
  53.  
  54.  
  55. int consistency1(int n, int k1, int k2) {
  56.  
  57. 	int ans = 0;
  58.  
  59. 	vector<int> pairsFrom(n);
  60. 	int s = 0, e = n-1;
  61. 	while(s<e){
  62. 		if(a[s] + a[e] > k2){
  63. 			e--;
  64. 		}
  65. 		else{
  66. 			pairsFrom[s] = n-e-1;
  67. 			s++;
  68. 		}
  69. 	}
  70. 	while(s<n){
  71. 		pairsFrom[s] = n-s-1;
  72. 		s++;
  73. 	}
  74.  
  75. 	vector<int> sPairs(n+1);
  76. 	for(int i=n-1; i>=0; i--){
  77. 		sPairs[i] = sPairs[i+1] + pairsFrom[i];
  78. 	}
  79.  
  80.  
  81. 	s = 0, e = n-3;
  82. 	while(s<e){
  83. 		if(a[s] + a[e] <= k1){
  84. 			s++;
  85. 		}
  86. 		else{
  87. 			int left = e-s;
  88. 			int right = sPairs[e+1];
  89.  
  90. 			ans += (left * right);
  91.  
  92. 			e--;
  93. 		}
  94. 	}
  95.  
  96. 	return ans;
  97.  
  98. }
  99.  
  100.  
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107. int consistency2(int n, int k1, int k2) {
  108.  
  109. 	int ans = 0;
  110.  
  111.  
  112. 	vector<int> pairsEndingAt(n);
  113. 	int s = 0, e = n-1;
  114. 	while(s<e){
  115. 		if(a[s] + a[e] <= k1){
  116. 			s++;
  117. 		}
  118. 		else{
  119. 			pairsEndingAt[e] = e-s;
  120. 			e--;
  121. 		}
  122. 	}
  123.  
  124.  
  125.  
  126. 	vector<int> pairsFrom(n);
  127. 	s = 0, e = n-1;
  128. 	while(s<e){
  129. 		if(a[s] + a[e] > k2){
  130. 			e--;
  131. 		}
  132. 		else{
  133. 			pairsFrom[s] = n-e-1;
  134. 			s++;
  135. 		}
  136. 	}
  137. 	while(s<n){
  138. 		pairsFrom[s] = n-s-1;
  139. 		s++;
  140. 	}
  141.  
  142. 	vector<int> sPairs(n+1);
  143. 	for(int i=n-1; i>=0; i--){
  144. 		sPairs[i] = sPairs[i+1] + pairsFrom[i];
  145. 	}
  146.  
  147.  
  148.  
  149. 	for(int j=1; j<n-2; j++){
  150.  
  151. 		int left= pairsEndingAt[j];
  152.  
  153. 		int right = sPairs[j+1];
  154.  
  155. 		ans += left*right;
  156. 	}
  157.  
  158. 	return ans;
  159. }
  160.  
  161.  
  162.  
  163.  
  164.  
  165.  
  166.  
  167.  
  168.  
  169.  
  170.  
  171.  
  172.  
  173.  
  174.  
  175.  
  176.  
  177.  
  178.  
  179. int practice(int n, int k1, int k2) {
  180.  
  181. 	return 0;
  182.  
  183. }
  184.  
  185.  
  186.  
  187.  
  188.  
  189.  
  190. void solve() {
  191.  
  192. 	int n, k1, k2;
  193. 	cin >> n >> k1 >> k2;
  194.  
  195. 	a.resize(n);
  196. 	for(int i=0; i<n; i++) cin >> a[i];
  197.  
  198.     cout << bruteforce(n, k1, k2) << " -> ";
  199.     cout << consistency1(n, k1, k2) << " ";
  200.     cout << consistency2(n, k1, k2) << endl;
  201.  
  202.  
  203.     // cout << bruteforce(n, k1, k2) << " -> ";
  204.     // cout << practice(n, k1, k2) << endl;
  205.  
  206. }
  207.  
  208.  
  209.  
  210.  
  211.  
  212. int32_t main() {
  213.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  214.  
  215.     int t = 1;
  216.     cin >> t;
  217.     while (t--) {
  218.         solve();
  219.     }
  220.  
  221.     return 0;
  222. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
2
9 4 4
1 2 2 3 3 4 5 5 5
8 9 7
1 2 3 4 5 6 8 12
stdout 
59 -> 59 59
2 -> 2 2
https://ideone.com/Mn8HvR
language:
C++14 (gcc 8.3)
created:
16 hours 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!