fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main(){
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.  
  9.     int t;
  10.     cin >> t;
  11.     while (t--) {
  12.         int n;
  13.         cin >> n;
  14.         vector<ll> x(n);
  15.         for (int i = 0; i < n; i++) {
  16.             cin >> x[i];
  17.         }
  18.  
  19.         // Pair each value with its original index, then sort by value
  20.         vector<pair<ll,int>> v(n);
  21.         for (int i = 0; i < n; i++) {
  22.             v[i] = { x[i], i };
  23.         }
  24.         sort(v.begin(), v.end());
  25.  
  26.         // Build prefix sums of the sorted values
  27.         vector<ll> pref(n+1, 0);
  28.         for (int i = 0; i < n; i++) {
  29.             pref[i+1] = pref[i] + v[i].first;
  30.         }
  31.         ll total = pref[n];
  32.  
  33.         // Compute answer for each sorted position
  34.         // sum_j |v[i].first - v[j].first|
  35.         //   = v[i].first * i   - pref[i]
  36.         //   + (total - pref[i+1]) - v[i].first * (n - i - 1)
  37.         // Then add +n for the “+1” per segment.
  38.         vector<ll> ans(n);
  39.         for (int i = 0; i < n; i++) {
  40.             ll xi = v[i].first;
  41.             ll left_cost  = xi * i - pref[i];
  42.             ll right_cost = (total - pref[i+1]) - xi * (n - i - 1);
  43.             ll sum_abs = left_cost + right_cost;
  44.             ans[v[i].second] = sum_abs + n;
  45.         }
  46.  
  47.         // Output in original order
  48.         for (int i = 0; i < n; i++) {
  49.             cout << ans[i] << (i+1<n ? ' ' : '\n');
  50.         }
  51.     }
  52.  
  53.     return 0;
  54. }
  55.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
3
3
1 4 3
5
1 2 5 7 1
4
1 10 100 1000
stdout
copy 
8 7 6
16 15 18 24 16
1111 1093 1093 2893
https://ideone.com/CpqUxt
language:
C++ (gcc 8.3)
created:
19 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!