Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <functional>
- #include <array>
- #include <iostream>
- #include <string>
- #include <vector>
- using namespace std;
- typedef long long ll;
- ll n,k;
- vector<pair<ll, ll>> a;
- vector<ll> pr;
- ll sm(ll position, ll i){
- ll left = 0, right = 0, sum = 0;
- ll c = k;
- if(position > i)
- position = i;
- if(position < i){
- ll pr_sum = 0;
- if(i - 1 >= 0){
- pr_sum += pr[i - 1];
- }
- if(position - 1 >= 0){
- pr_sum -= pr[position - 1];
- }
- sum += (i - position) * a[i].first - pr_sum;
- c -= (i - position);
- }
- sum += (pr[i + c] - pr[i]) - a[i].first * c;
- return sum;
- }
- int main() {
- cin >> n >> k;
- for(int i = 0; i < n; ++i) {
- ll x;
- cin >> x;
- a.push_back(make_pair(x,i));
- }
- sort(a.begin(), a.end());
- pr.resize(n,0);
- pr[0] = a[0].first;
- for(int i = 1; i < n; ++i){
- pr[i] = pr[i - 1] + a[i].first;
- }
- ll pos = 0;
- vector<ll> ans(n);
- for(int i = 0; i < n; ++i){
- while(pos + 1 <= i && pos + k + 1 < n && sm(pos + 1,i) < sm(pos,i))
- pos++;
- ans[a[i].second] = sm(pos,i);
- }
- for(int i = 0; i < n; ++i){
- cout << ans[i] << " ";
- }
- cout << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement