fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int              long long int
  4. #define double           long double
  5. #define print(a)         for(auto x : a) cout << x << " "; cout << endl
  6. inline int power(int a, int b) {
  7.     int x = 1;
  8.     while (b) {
  9.         if (b & 1) x *= a;
  10.         a *= a;
  11.         b >>= 1;
  12.     }
  13.     return x;
  14. }
  15.  
  16.  
  17. const int M = 1000000007;
  18. const int N = 3e5+9;
  19. const int INF = 2e9+1;
  20. const int LINF = 2000000000000000001;
  21.  
  22. //_ ***************************** START Below *******************************
  23.  
  24.  
  25.  
  26. typedef pair<int,int> pii;
  27.  
  28. vector<int> a;
  29.  
  30.  
  31. void rebalance(set<pii, greater<pii>>& leftMax, set<pii>& rightMin, int& leftSum, int& rightSum){
  32.  
  33. 	if(leftMax.size() > rightMin.size()){
  34. 		auto left = *leftMax.begin();
  35. 		leftMax.erase(left);
  36.  
  37. 		leftSum -= left.first;
  38. 		rightSum += left.first;
  39.  
  40. 		rightMin.insert(left);
  41. 	}
  42. 	else if(rightMin.size() > leftMax.size()+1){
  43. 		auto right = *rightMin.begin();
  44. 		rightMin.erase(right);
  45.  
  46. 		rightSum -= right.first;
  47. 		leftSum += right.first;
  48.  
  49. 		leftMax.insert(right);
  50. 	}
  51.  
  52. 	if(!leftMax.empty() && !rightMin.empty() && leftMax.begin()->first > rightMin.begin()->first ){
  53. 		auto left = *leftMax.begin(); 
  54. 		auto right = *rightMin.begin();
  55.  
  56.  
  57. 		leftMax.erase(left);
  58. 		rightMin.erase(right);
  59.  
  60. 		leftSum -= left.first;
  61. 		rightSum -= right.first;
  62.  
  63. 		leftMax.insert(right);
  64. 		leftSum += right.first;
  65.  
  66. 		rightMin.insert(left);
  67. 		rightSum += left.first;
  68. 	}
  69.  
  70. }
  71.  
  72. vector<int> consistency(int n, int k) {
  73.  
  74. 	vector<int> ans;
  75.  
  76. 	set<pii> rightMin;
  77. 	int rightSum = 0;
  78.  
  79. 	set<pii, greater<pii> > leftMax;
  80. 	int leftSum = 0;
  81.  
  82. 	int s = 0, e = 0;
  83. 	while(e<n){
  84. 		leftSum += a[e];
  85. 		leftMax.insert({a[e], e});
  86. 		rebalance(leftMax, rightMin, leftSum, rightSum);
  87.  
  88. 		if(e-s+1 < k){
  89. 			e++;
  90. 		}
  91. 		else{
  92. 			auto left = *leftMax.begin();
  93. 			auto right = *rightMin.begin();
  94.  
  95. 			int x = left.first;
  96. 			int y = right.first;
  97.  
  98. 			int m = y;
  99. 			if( !(k&1) ) m = (x+y)/2;
  100.  
  101. 			int cost = (k/2) * m - leftSum;
  102. 			cost +=  rightSum - ((k+1)/2) * m;
  103.  
  104. 			ans.push_back(cost);
  105.  
  106. 			if(leftMax.count({a[s], s})){
  107. 				leftMax.erase({a[s], s});
  108. 				leftSum -= a[s];
  109. 			}
  110. 			else{
  111. 				rightMin.erase({a[s], s});
  112. 				rightSum -= a[s];
  113. 			}
  114. 			rebalance(leftMax, rightMin, leftSum, rightSum);
  115.  
  116. 			s++;
  117. 			e++;
  118. 		}
  119. 	}
  120.  
  121. 	return ans;
  122.  
  123. }
  124.  
  125.  
  126.  
  127.  
  128.  
  129.  
  130.  
  131.  
  132.  
  133.  
  134.  
  135.  
  136.  
  137.  
  138.  
  139.  
  140.  
  141.  
  142.  
  143. // typedef pair<int,int> pii;
  144.  
  145. vector<int> practice(int n, int k) {
  146.  
  147.  
  148. }
  149.  
  150.  
  151.  
  152.  
  153.  
  154.  
  155.  
  156.  
  157. void solve() {
  158.  
  159.     int n, k;
  160.     cin>>n >> k;
  161.  
  162. 	a.resize(n);
  163.     for(int i=0; i<n; i++) cin >> a[i];
  164.  
  165.     auto ans1 = consistency(n, k);
  166.     for(auto& it : ans1 )	cout << it << " "; cout << endl;
  167.  
  168.  
  169. 	// auto p = practice(n, k);
  170. 	// for(auto& t : p) cout << t << " "; cout << endl;
  171.  
  172.  
  173.  
  174. }
  175.  
  176.  
  177.  
  178.  
  179.  
  180. int32_t main() {
  181.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  182.  
  183.     int t = 1;
  184.     while (t--) {
  185.         solve();
  186.     }
  187.  
  188.     return 0;
  189. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
8 3
2 4 3 5 8 1 2 1
stdout
copy 
2 2 5 7 7 1
https://ideone.com/BC65oU
language:
C++14 (gcc 8.3)
created:
1 day 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!