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. set<pii, greater<pii> > leftMax;
  31. set<pii> rightMin;
  32.  
  33. void rebalance(int& leftSum, int& rightSum){
  34.  
  35.     if(!leftMax.empty() && !rightMin.empty() && (*rightMin.begin()).first < (*leftMax.begin()).first ){
  36.         auto leftTop = *leftMax.begin();
  37.         auto rightTop = *rightMin.begin();
  38.  
  39.         leftMax.erase(leftTop);
  40.         rightMin.erase(rightTop);
  41.  
  42.         leftSum -= leftTop.first;
  43.         leftSum += rightTop.first;
  44.  
  45.         rightSum -= rightTop.first;
  46.         rightSum += leftTop.first;
  47.  
  48.         leftMax.insert(rightTop);
  49.         rightMin.insert(leftTop);
  50.     }
  51.  
  52.     if(leftMax.size() > rightMin.size()){
  53.         auto leftTop = *leftMax.begin();
  54.         leftMax.erase(leftTop);
  55.         rightMin.insert(leftTop);
  56.  
  57.         leftSum -= leftTop.first;
  58.         rightSum += leftTop.first;
  59.     }
  60.     else if(rightMin.size() > leftMax.size()+1 ){
  61.         auto rightTop = *rightMin.begin();
  62.         rightMin.erase(rightTop);
  63.         leftMax.insert(rightTop);
  64.  
  65.         rightSum -= rightTop.first;
  66.         leftSum += rightTop.first;
  67.     }
  68. }
  69.  
  70.  
  71. vector<int> consistency1(int n, int k) {
  72.     vector<int> ans;
  73.  
  74.     int leftSum = 0;
  75.     int rightSum = 0;
  76.  
  77.     int s = 0, e = 0;
  78.     while(e < n){
  79.         leftMax.insert({a[e], e});
  80.         leftSum += a[e];
  81.         rebalance(leftSum, rightSum);
  82.  
  83.  
  84.         if(e - s + 1 < k){
  85.             e++;
  86.         }
  87.         else{
  88.             auto rightTop = *rightMin.begin();
  89.             int median = rightTop.first;
  90.  
  91.             if( !(k & 1) ) {
  92.                 auto leftTop = *leftMax.begin();
  93.                 median = (leftTop.first + rightTop.first) / 2;
  94.             }
  95.  
  96.             int cost = ((k / 2) * median - leftSum) + (rightSum - ((k + 1) / 2) * median);
  97.             ans.push_back(cost);
  98.  
  99.             if(leftMax.count({a[s], s})){
  100.                 leftMax.erase({a[s],s});
  101.                 leftSum -= a[s];
  102.             }
  103.             else {
  104.                 rightMin.erase({a[s],s});
  105.                 rightSum -= a[s];
  106.             }
  107.             rebalance(leftSum, rightSum);
  108.  
  109.             s++;
  110.             e++;
  111.         }
  112.     }
  113.  
  114.     return ans;
  115. }
  116.  
  117.  
  118.  
  119.  
  120.  
  121.  
  122.  
  123.  
  124.  
  125.  
  126.  
  127.  
  128. void solve() {
  129.  
  130.     int n, k;
  131.     cin>>n >> k;
  132.  
  133. 	a.resize(n);
  134.     for(int i=0; i<n; i++) cin >> a[i];
  135.  
  136.     auto ans1 = consistency1(n, k);
  137.     for(auto& it : ans1 ) {
  138.         cout << it << " ";
  139.     }
  140.     cout << endl;
  141.  
  142.  
  143.  
  144.  
  145.  
  146.  
  147. }
  148.  
  149.  
  150.  
  151.  
  152.  
  153. int32_t main() {
  154.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  155.  
  156.     int t = 1;
  157.     while (t--) {
  158.         solve();
  159.     }
  160.  
  161.     return 0;
  162. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
8 3
2 4 3 5 8 1 2 1
stdout
copy 
2 2 5 7 7 1
https://ideone.com/oguWdv
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!