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.  
  20. //* Template1 for Atmost k (i.e. <= k )
  21.  
  22. //* 	We Start with Valid window
  23. //* 	Keep expanding valid window and computing results (till it's valid)
  24. //* 	Once it's invalid, keep shrinking untill it becomes valid again
  25. //* 		On becoming valid, Compute result and epxand again
  26.  
  27.  
  28. //* Count + Atmost K 
  29. //* Count subarrays with sum <= k
  30.  
  31. void consistency1(int n, int k){
  32.  
  33. 	int s = 0, e = 0;
  34. 	int sum = 0;
  35. 	int ans = 0;
  36.  
  37.  
  38. 	while(e<n){
  39. 		//* Calculate state
  40. 		sum += a[e];
  41.  
  42.  
  43. 		if(sum < k){
  44. 			//* Valid Wndow => Compute Result && expand 
  45. 			ans += (e-s+1);
  46. 			e++;
  47. 		}
  48. 		else if(sum==k){
  49. 			//* Note : In problem we have sum<k as valid, not sum<=k as valid
  50. 			//* Valid Wndow => Compute result && expand 
  51. 			ans += (e-s+1);
  52. 			e++;
  53. 		}
  54. 		else{
  55. 			//* Invalid window => Keep Shrink Window
  56. 			//* Allow single element to be checked with s<=e
  57. 			while(s<=e && sum>k){
  58.  
  59. 				//* Note : In problem we have sum<k as valid so it would be sum>=k
  60. 				sum -= a[s];
  61. 				s++;
  62. 			}
  63.  
  64. 			//* Valid window => Compute Result && expand 
  65. 			if(sum<=k) ans += (e-s+1);
  66. 			e++;
  67. 		}
  68. 	}
  69.  
  70. 	cout << ans << endl;
  71.  
  72. }
  73.  
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80. //* Template2 for Atmost k (i.e. <= k )
  81. //* 	(based on Cache Invalidation) 
  82.  
  83. //* 	We Start with Valid window
  84. //* 	If Window is Invalid 
  85. //* 		(similar to Cache Invalidation)
  86. //* 		Keep shrinking till it becomes valid
  87. //* 	Now window is becomes valid 
  88. //* 		Compute  result
  89.  
  90.  
  91. void consistency2(int n, int k){
  92.  
  93. 	int sum = 0;
  94. 	int ans = 0;
  95. 	for(int s=0, e=0; e<n; e++){
  96.  
  97. 		//* Calculate state
  98. 		sum += a[e];
  99.  
  100. 		//* Invalid window => Shrink 
  101. 		//* Allow single element to be checked with s<=e
  102. 		while(s<=e && sum>k){
  103. 			//* Note : In problem we have sum<k as valid so it would be sum>=k
  104. 			sum -= a[s];
  105. 			s++;
  106. 		}
  107.  
  108. 		//* Valid window guranteed => Compute Result
  109. 		//* Note : In problem we have sum<k as valid, not sum<=k as valid
  110. 		if(sum<=k) ans += (e-s+1);
  111. 	}
  112.  
  113. 	cout << ans << endl;
  114.  
  115. }
  116.  
  117.  
  118.  
  119.  
  120.  
  121. void solve() {
  122.  
  123. 	int n, k;
  124. 	cin >> n >> k;
  125. 	a.resize(n);
  126. 	for(int i=0; i<n; i++) cin >> a[i];
  127.  
  128. 	consistency1(n, k);
  129. 	consistency2(n, k);
  130.  
  131. }
  132.  
  133.  
  134.  
  135.  
  136.  
  137. int32_t main() {
  138.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  139.  
  140.     int t = 1;
  141.     while (t--) {
  142.         solve();
  143.     }
  144.  
  145.     return 0;
  146. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
6 4
1 1 2 1 4 5
stdout
copy 
10
10
https://ideone.com/yFUNio
language:
C++14 (gcc 8.3)
created:
7 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!