fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. inline int power(int a, int b) {
  6.     int x = 1;
  7.     while (b) {
  8.         if (b & 1) x *= a;
  9.         a *= a;
  10.         b >>= 1;
  11.     }
  12.     return x;
  13. }
  14.  
  15.  
  16. const int M = 1000000007;
  17. const int N = 3e5+9;
  18. const int INF = 2e9+1;
  19. const int LINF = 2000000000000000001;
  20.  
  21. //_ ***************************** START Below *******************************
  22.  
  23.  
  24.  
  25. vector<int> a;
  26.  
  27.  
  28. void bruteforce(int n, int k1, int k2){
  29. 	int ans = 0;
  30.  
  31. 	for(int i=0; i<n-3; i++){
  32. 		for(int j=i+1; j<n-2; j++){
  33. 			int leftSum = a[i] + a[j];
  34. 			if(leftSum <= k1) continue;
  35.  
  36. 			for(int k=j+1; k<n-1; k++){
  37. 				for(int l=k+1; l<n; l++){
  38. 					int rightSum = a[k] + a[l];
  39. 					if(rightSum > k2 ) ans++;
  40. 				}
  41. 			}
  42. 		}
  43. 	}
  44. 	cout << ans << " ";
  45. }
  46.  
  47. //* O(n^2)
  48. void consistency1(int n, int k1, int k2) {
  49.  
  50. 	int ans = 0;
  51. 	for(int j=1; j<n-2; j++){
  52. 		int i=0;
  53. 		while(i<j){
  54. 			if(a[i] + a[j] > k1) break;
  55. 			i++;
  56. 		}
  57. 		int leftCt = j-i;
  58.  
  59. 		int  s= j+1, e = n-1;
  60. 		int rightCt = 0;
  61. 		while(s<e){
  62. 			int sum = a[s] + a[e];
  63. 			if(sum > k2){
  64. 				rightCt += (e-s);
  65. 				e--;
  66. 			}
  67. 			else{
  68. 				s++;
  69. 			}
  70. 		}
  71. 		ans += leftCt * rightCt;
  72. 	}
  73.  
  74. 	cout << ans << " ";
  75. }
  76.  
  77.  
  78.  
  79.  
  80. //* O(n*logn + n + n*logn) == O(n*logn)
  81. void consistency2(int n, int k1, int k2) {
  82.  
  83. 	int ans = 0;
  84.  
  85. 	vector<int> p(n);
  86. 	for(int i=0; i<n-1; i++){
  87. 		int target = k2 - a[i];
  88. 		int j = upper_bound(a.begin() + i + 1, a.end(), target) - a.begin();
  89. 		p[i] = n-j;
  90. 	}
  91. 	vector<int> rightSufix(n);
  92. 	for(int i=n-2; i>=0; i--){
  93. 		rightSufix[i] = rightSufix[i+1] + p[i];
  94. 	}
  95.  
  96.  
  97. 	for(int j=1; j<n-2; j++){
  98. 		int target = k1 - a[j];
  99. 		int i = upper_bound(a.begin(), a.begin()+j, target) - a.begin();
  100. 		int leftCt = j-i;
  101.  
  102. 		int rightCt = rightSufix[j+1];
  103.  
  104. 		ans += leftCt * rightCt;
  105.  
  106. 	}
  107.  
  108.  
  109. 	cout << ans << " ";
  110.  
  111. }
  112.  
  113.  
  114. //* Left Count Pre Computation  : 
  115.  
  116. //* Eg : [ 1 , 2 , 3 , 4 , 5 , 6 , 8 ]   k1 = 9
  117.  
  118. //* Ending at analogy : 
  119. //* 	We are finding pairs (x,y) with sum x+y == k1 ending at y
  120.  
  121. //* Observation : if we drew out patterns for each pairs , it looks like this : 
  122. //*      [ (1 , 2 , (3 , (4 , 5) , 6) , 8) ]   
  123. //*     	y = 1,2,3,4 can't form pair with any x such that x+y >= 9
  124. //* 	    y = 5 forms pair with x = 4 only               => ct = 1
  125. //* 		y = 6 forms pair with x = (3, 4, 5)            => ct = 3
  126. //* 		y = 8 forms pair with x = (1, 2, 3, 4, 5, 6)   => ct = 6
  127.  
  128. //* 	Now we can use 2 ptr from 1st pair [x, x+1] such that x + x + 1 >= k1
  129. //* 	                i   j
  130. //*      [ 1 , 2 , 3 , (4 , 5) , 6 , 8) ]   
  131. //* 			p[5] = max(0, 2) = 2
  132. //* 		Now we want to maximize p[5] cts so move i left => i--
  133.  
  134. //* 	           i        j
  135. //*      [ 1 , 2 , 3 , (4 , 5) , 6 , 8) ]   
  136. //* 			5+3 < k1
  137. //* 		Invalid so move to next y => j++
  138.  
  139. //* 	                i       j
  140. //*      [ 1 , 2 , 3 , (4 , 5 , 6) , 8) ]   
  141. //* 			p[6] = max(0, 3) = 3
  142.  
  143. //* 	            i           j
  144. //*      [ 1 , 2 , (3 , 4 , 5 , 6) , 8) ]   
  145. //* 			p[6] = max(3, 4) = 4
  146.  
  147. //* 	        i               j
  148. //*      [ 1 , (2 , 3 , 4 , 5 , 6) , 8) ]   
  149. //* 			Invalid => j++
  150.  
  151. //* O(n + n + n ) = O(n)
  152. void consistency3(int n, int k1, int k2) {
  153.  
  154. 	int ans = 0;
  155.  
  156. 	vector<int> p(n);
  157.  
  158. 	vector<int> leftPrefix(n);
  159. 	int i=1;
  160. 	while(i<n){
  161. 		if(a[i] + a[i-1] >= k1) break;
  162. 		i++;
  163. 	}
  164. 	int left = i-1;
  165. 	int right = i;
  166.  
  167. 	while(left>=0 && right<n){
  168. 		if(a[left] + a[right] > k1){
  169. 			p[right] = max(p[right], right-left);
  170. 			left--;
  171. 		}
  172. 		else {
  173. 			right++;
  174. 		}
  175. 	}
  176. 	for(int i=1; i<n; i++){
  177. 		leftPrefix[i] = leftPrefix[i-1] + p[i];
  178. 	}
  179.  
  180.  
  181.  
  182. 	vector<int> q(n);
  183.  
  184. 	vector<int> rightSufix(n);
  185. 	// for(int i=n-1; i>=0; i--){
  186. 	// 	rightSufix[i] = rightSufix[i+1] + q[i];
  187. 	// }
  188.  
  189. 	for(int j=1; j<n-2; j++){
  190. 		int leftCt = leftPrefix[j];
  191. 		int rightCt = rightSufix[j+1]; 
  192.  
  193. 		ans += leftCt * rightCt;
  194. 	}
  195.  
  196.  
  197. 	cout << ans << " ";
  198.  
  199. }
  200.  
  201.  
  202. void solve() {
  203.  
  204. 	int n, k1, k2;
  205. 	cin >> n >> k1 >> k2;
  206.  
  207. 	a.resize(n);
  208. 	for(int i=0; i<n; i++) cin >> a[i];
  209.  
  210.     bruteforce(n, k1, k2);
  211.     consistency1(n, k1, k2);
  212.     consistency2(n, k1, k2);
  213.     consistency3(n, k1, k2);
  214.  
  215.     cout << endl;
  216.  
  217. }
  218.  
  219.  
  220.  
  221.  
  222.  
  223. int32_t main() {
  224.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  225.  
  226.     int t = 1;
  227.     // cin >> t;
  228.     while (t--) {
  229.         solve();
  230.     }
  231.  
  232.     return 0;
  233. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
8 9 7
1 2 3 4 5 6 8 12
stdout
copy 
2 2 2 0
https://ideone.com/RHwyNQ
language:
C++14 (gcc 8.3)
created:
2 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!