# 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