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