fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define fast_io ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  5. #define cout_precision cout.setf(ios::fixed); cout.precision(32);
  6. #define clr(a) memset(a,0,sizeof(a))
  7. #define umap unordered_map
  8. #define uset unordered_set
  9. #define fr first
  10. #define sc second
  11. #define pb push_back
  12. #define pf push_front
  13. #define M int(1e9+7)
  14. #define endl '\n'
  15. #define largest(a,b,c) (a>b?(a>c? a:c):(b>c? b:c))
  16. #define smallest(a,b,c) (a<b?(a<c? a:c):(b<c? b:c))
  17.  
  18. using ll = int64_t; using vll = vector<ll>; using vvll = vector<vll>;
  19. using pll = pair<ll, ll>; using vpll = vector<pll>; using vvpll = vector<vpll>;
  20.  
  21. ll power(ll a, ll n){
  22. 	if(n == 0)	return 1;
  23. 	if(n == 1)	return a%M;
  24. 	if(n&1){
  25. 		return a*power(a,n-1);
  26. 	}
  27. 	ll res = power(a,n/2);
  28. 	return (res*res)%M;
  29. }
  30.  
  31. int main() {
  32. 	fast_io; cout_precision;
  33. 	int t;	cin >> t;
  34. 	while(t--){
  35. 		ll n,k;	cin >> n >> k;
  36. 		vector <ll> arr(n);
  37. 		for(int i=0; i<n; i++){
  38. 			cin >> arr[i];
  39. 		}
  40. 		vector <ll> pref(n);
  41. 		pref[0] = arr[0];
  42. 		for(int i=1; i<n; i++){
  43. 			pref[i] = pref[i-1] + arr[i];
  44. 		}
  45.  
  46. 		ll res = 0;
  47. 		ll currMedian  = arr[0] ;
  48. 		ll currAvg = pref[k-1]/k;
  49.  
  50. 		multiset <ll , greater <ll> > maxHeap;
  51. 		multiset < ll> minHeap;
  52.  
  53. 		maxHeap.insert(arr[0]);
  54.  
  55. 		for(int i=1; i<k; i++){
  56. 			if(maxHeap.size() > minHeap.size()){
  57. 				if(arr[i] < currMedian){
  58. 					minHeap.insert(*(maxHeap.begin()));
  59. 					maxHeap.erase(maxHeap.find(*maxHeap.begin()));
  60. 					maxHeap.insert(arr[i]);
  61. 				}
  62. 				else{
  63. 					minHeap.insert(arr[i]);
  64. 				}
  65. 				currMedian = *maxHeap.begin();
  66. 			}
  67. 			else if(maxHeap.size() < minHeap.size()){
  68. 				if(arr[i] > currMedian){
  69. 					maxHeap.insert(*minHeap.begin());
  70. 					minHeap.erase(minHeap.find(*(minHeap.begin())));
  71. 					minHeap.insert(arr[i]);
  72. 				}
  73. 				else{
  74. 					maxHeap.insert(arr[i]);
  75. 				}
  76. 				currMedian = *maxHeap.begin();
  77. 			}
  78. 			else{
  79. 				if(arr[i] < currMedian){
  80. 					maxHeap.insert(arr[i]);
  81. 					currMedian = *maxHeap.begin();
  82. 				}
  83. 				else{
  84. 					minHeap.insert(arr[i]);
  85. 					currMedian = *minHeap.begin();
  86. 				}
  87. 			}
  88. 		}
  89.  
  90. 		if(currAvg >= currMedian)	res++;
  91.  
  92. 		for(int i=k; i<n; i++){
  93. 			if(maxHeap.find(arr[i-k]) != maxHeap.end()){
  94. 				maxHeap.erase(maxHeap.find(arr[i-k]));
  95. 			}
  96. 			else{
  97. 				minHeap.erase(minHeap.find(arr[i-k]));
  98. 			}
  99.  
  100. 			if(maxHeap.size() > minHeap.size()){
  101. 				if(arr[i] < currMedian){
  102. 					minHeap.insert(*(maxHeap.begin()));
  103. 					maxHeap.erase(maxHeap.find(*maxHeap.begin()));
  104. 					maxHeap.insert(arr[i]);
  105. 				}
  106. 				else{
  107. 					minHeap.insert(arr[i]);
  108. 				}
  109. 				currMedian = *maxHeap.begin();
  110. 			}
  111. 			else if(maxHeap.size() < minHeap.size()){
  112. 				if(arr[i] > currMedian){
  113. 					maxHeap.insert(*minHeap.begin());
  114. 					minHeap.erase(minHeap.find(*(minHeap.begin())));
  115. 					minHeap.insert(arr[i]);
  116. 				}
  117. 				else{
  118. 					maxHeap.insert(arr[i]);
  119. 				}
  120. 				currMedian = *maxHeap.begin();
  121. 			}
  122. 			else{
  123. 				if(arr[i] < currMedian){
  124. 					maxHeap.insert(arr[i]);
  125. 					currMedian = *maxHeap.begin();
  126. 				}
  127. 				else{
  128. 					minHeap.insert(arr[i]);
  129. 					currMedian = *minHeap.begin();
  130. 				}
  131. 			}
  132.  
  133.  
  134. 			currAvg = (pref[i] - pref[i-k])/k;
  135.  
  136. 			if(currAvg >= currMedian){
  137. 				res++;
  138. 			}
  139. 		}
  140.  
  141. 		cout << res <<endl;
  142. 	}
  143.  
  144.  
  145.  
  146.  
  147. 	return 0;
  148. }
Runtime error #stdin #stdout #stderr 0s 4484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/gDi1po
language:
C++ (gcc 8.3)
created:
3 years 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!