fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long int
  4. const int MOD = 1000000007;
  5.  
  6. // Fenwick Tree for efficient prefix sum queries and updates
  7. class FenwickTree {
  8. public:
  9.     vector<int> fenwick;
  10.     FenwickTree(int n) {
  11.         fenwick.resize(n + 1, 0);
  12.     }
  13.  
  14.     void update(int idx, int val) {
  15.         for (; idx < fenwick.size(); idx += idx & -idx) {
  16.             fenwick[idx] += val;
  17.         }
  18.     }
  19.  
  20.     int query(int idx) {
  21.         int sum = 0;
  22.         for (; idx > 0; idx -= idx & -idx) {
  23.             sum += fenwick[idx];
  24.         }
  25.         return sum;
  26.     }
  27. };
  28.  
  29. int32_t main() {
  30.     int t;
  31.     cin >> t;
  32.     while (t--) {
  33.         int n, k;
  34.         cin >> n >> k;
  35.  
  36.         vector<int> p(n);
  37.         for (int i = 0; i < n; i++) {
  38.             cin >> p[i];
  39.         }
  40.  
  41.         sort(p.begin(), p.end());
  42.  
  43.         // Initialize Fenwick Tree for prefix sums
  44.         FenwickTree fenwick(n);
  45.  
  46.         for (int i = 0; i < n; i++) {
  47.             fenwick.update(i + 1, p[i]);  // 1-based indexing for Fenwick Tree
  48.         }
  49.  
  50.         // Process each length m
  51.         for (int m = 1; m <= n; m++) {
  52.             int rem = m, cost = 0, idx = m;
  53.  
  54.             // Calculate segments required
  55.             int segments = (rem + k) / (k + 1);
  56.             if (segments * (k + 1) < rem) segments++;
  57.  
  58.             for (int i = 0; i < segments && rem > 0; i++) {
  59.                 int take = min(k, rem);
  60.                 if (idx - take >= 0) {
  61.                     cost += fenwick.query(idx) - fenwick.query(idx - take);
  62.                 }
  63.                 idx -= (take + 1);
  64.                 rem -= (take + 1);
  65.             }
  66.  
  67.             cout << cost << " ";
  68.         }
  69.         cout << "\n";
  70.     }
  71.     return 0;
  72. }
  73.  
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
2
5 2
1 2 4 6 10
3 2
1 1 1
stdout
copy 
1 3 6 11 19 
1 2 2
https://ideone.com/5Xlaci
language:
C++ (gcc 8.3)
created:
5 days 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!