Advertisement
OIQ

Untitled

OIQ
Jul 31st, 2021
67
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.25 KB | None
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <map>
  5.  
  6.  
  7. using namespace std;
  8.  
  9. #define ll long long
  10. vector < pair <ll , ll >> a;
  11. vector <ll> pref;
  12.  
  13.  
  14. int countRes(ll l, ll r, ll i) {
  15. ll lsum = pref[i] - pref[l - 1];
  16. ll rsum = pref[r] - pref[max(i, l)];
  17.  
  18. ll res = (rsum - a[i].first * (r - i)) + (max(a[i].first * (i - l + 1) - lsum, 0LL));
  19.  
  20. return res;
  21. }
  22.  
  23. int main() {
  24. ll n, k;
  25. cin >> n >> k;
  26. a.resize(1);
  27. for (int i = 1; i <= n; i++) {
  28. int c;
  29. cin >> c;
  30. a.push_back({ c, i });
  31. }
  32. pref.resize(n + 1);
  33. sort(begin(a), end(a));
  34. // pref[0] = a[0].first;
  35. for (int i = 1; i <= n; i++)
  36. pref[i] = pref[i - 1] + a[i].first;
  37.  
  38. ll l = 1;
  39. ll r = k + 1LL;
  40. map<ll, ll> ans;
  41.  
  42. for (int i = 1; i <= n; i++) {
  43. if (i > r) {
  44. r = i;
  45. l = r - k;
  46. }
  47. ll res = countRes(l, r, i);
  48. ll tmp;
  49. while (r != n && res > (tmp = countRes(l + 1, r + 1, i))) {
  50. res = tmp;
  51. l++; r++;
  52. }
  53. if (ans.find(a[i].first) == ans.end())
  54. ans[a[i].first] = res;
  55. else
  56. ans[a[i].first] = min(res, ans[a[i].first]);
  57. }
  58.  
  59. sort(a.begin(), a.end(), [](auto& left, auto& right) {
  60. return left.second < right.second;
  61. });
  62.  
  63. for (int i = 1; i <= n; i++)
  64. cout << ans[a[i].first] << " ";
  65.  
  66. return 0;
  67.  
  68.  
  69. }
Advertisement
RAW Paste Data Copied
Advertisement