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