deushiro

xds

Jul 31st, 2021
958
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <functional>
  3. #include <array>
  4. #include <iostream>
  5. #include <string>
  6. #include <vector>
  7.  
  8.  
  9.  
  10. using namespace std;
  11.  
  12.  
  13. typedef long long ll;
  14.  
  15. ll n,k;
  16. vector<pair<ll, ll>> a;
  17. vector<ll> pr;
  18.  
  19. ll sm(ll position, ll i){
  20.     ll left = 0, right = 0, sum = 0;
  21.     ll c = k;
  22.     if(position > i)
  23.         position = i;
  24.     if(position < i){
  25.         ll pr_sum = 0;
  26.         if(i - 1 >= 0){
  27.             pr_sum += pr[i - 1];
  28.         }
  29.         if(position - 1 >= 0){
  30.             pr_sum -= pr[position - 1];
  31.         }
  32.         sum += (i - position) * a[i].first - pr_sum;
  33.         c -= (i - position);
  34.     }
  35.     sum += (pr[i + c] - pr[i]) - a[i].first * c;
  36.     return sum;
  37. }
  38.  
  39.  
  40. int main() {
  41.  
  42.     cin >> n >> k;
  43.     for(int i = 0; i < n; ++i) {
  44.         ll x;
  45.         cin >> x;
  46.         a.push_back(make_pair(x,i));
  47.     }
  48.     sort(a.begin(), a.end());
  49.     pr.resize(n,0);
  50.     pr[0] = a[0].first;
  51.     for(int i = 1; i < n; ++i){
  52.         pr[i] = pr[i - 1] + a[i].first;
  53.     }
  54.     ll pos = 0;
  55.     vector<ll> ans(n);
  56.     for(int i = 0; i < n; ++i){
  57.         while(pos + 1 <= i && pos + k + 1 < n && sm(pos + 1,i) < sm(pos,i))
  58.             pos++;
  59.         ans[a[i].second] = sm(pos,i);
  60.     }
  61.     for(int i = 0; i < n; ++i){
  62.         cout << ans[i] << " ";
  63.     }
  64.     cout << endl;
  65.  
  66. }
RAW Paste Data