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 ans = 0;	
  25. 	int sum = 0;
  26.  
  27.  
  28. 	while(e<n){
  29. 	    sum += a[e];
  30. 	    if(sum <= k){
  31. 	    	ans += e-s+1;
  32. 	        e++;
  33. 	    }
  34. 	    else{
  35. 	        while(s<=e && sum>k){
  36. 	            sum -= a[s];
  37. 	            s++;
  38. 	        }
  39. 	        if(sum==k) ans += e-s+1;
  40. 	        e++;
  41. 	    }
  42. 	}	
  43.     return ans;
  44. }
  45.  
  46. int consistency1(int n, int k){
  47.  
  48. 	return atmostK(n, k) - atmostK(n, k-1);
  49.  
  50. }
  51.  
  52.  
  53.  
  54.  
  55. //* Template 1
  56.  
  57.  
  58. int consistency2(int n, int k){
  59.  
  60. 	int big = 0, small = 0;	
  61. 	int s = 0, e = 0;
  62. 	int l = 0;
  63. 	int ans = 0;	
  64.  
  65. 	while(e<n){
  66. 	    big += a[e];
  67. 	    small += a[e];	
  68.  
  69. 	    while(l<=e && small >= k){
  70. 	        small -= a[l];
  71. 	        l++;
  72. 	    }	
  73.  
  74.  
  75. 	    if(big < k){
  76. 	        e++;
  77. 	    }
  78. 	    else{
  79. 	        while(s<=e && big>k){
  80. 	            big -= a[s];
  81. 	            s++;
  82. 	        }
  83.  
  84. 	        ans += l-s;
  85. 	        e++;
  86. 	    }
  87. 	}	
  88. 	return ans;
  89.  
  90. }
  91.  
  92.  
  93.  
  94.  
  95. //* Template 2
  96.  
  97. int consistency3(int n, int k){
  98.  
  99. 	int big = 0, small = 0;	
  100. 	int ans = 0;	
  101.  
  102. 	for(int j=0, i=0, l=0; j<n; j++){
  103. 	    big += a[j];
  104. 	    small += a[j];	
  105. 	    while(l<=j && small >= k){
  106. 	        small -= a[l];
  107. 	        l++;
  108. 	    }	
  109.  
  110. 	    while(i<=j && big>k){
  111. 	        big -= a[i];
  112. 	        i++;
  113. 	    }
  114. 	    ans += l-i;
  115. 	}	
  116.  
  117. 	return ans;
  118. }
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136. int practice(int n, int k){
  137.  
  138. 	return 0;	
  139. }
  140.  
  141.  
  142.  
  143.  
  144. void solve() {
  145.  
  146. 	int n, k;
  147. 	cin >> n >> k;
  148. 	a.resize(n);
  149. 	for(int i=0; i<n; i++) cin >> a[i];
  150.  
  151. 	cout << consistency1(n, k) << " " << consistency2(n,k) <<  " " << consistency3(n,k) << endl;
  152.  
  153. 	// cout << consistency1(n, k) << " -> " << practice(n, k) << endl;
  154.  
  155. }
  156.  
  157.  
  158.  
  159.  
  160.  
  161. int32_t main() {
  162.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  163.  
  164.     int t = 1;
  165.     cin >> t;
  166.     while (t--) {
  167.         solve();
  168.     }
  169.  
  170.     return 0;
  171. }
Success #stdin #stdout 0s 5288KB
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/QypFzd
language:
C++14 (gcc 8.3)
created:
15 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!