Submission #60580448

---

Source Code Expand

#include <bits/stdc++.h>
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
using namespace std;

struct Node {
  int64_t val;
  Node* l;
  Node* r;

  Node(int64_t val_) : val(val_), l(nullptr), r(nullptr) {}
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, k;
  cin >> n >> k;
  vector<int64_t> a(n);
  for (int i = 0; i < n; i++) cin >> a[i];
  if (k == 1) {
    sort(a.rbegin(), a.rend());
    int64_t ans = 0;
    for (int i = 0; i < n; i++) {
      ans += a[i];
      cout << ans << " \n"[i == n - 1];
    }
    return 0;
  }
  int m = n / k;
  vector<Node*> b;
  for (int i = 0; i + k - 1 < n; i++) {
    int64_t sum = 0;
    for (int j = i; j <= i + k - 1; j++) sum += a[j];
    b.push_back(new Node(sum));
  }
  set<pair<int64_t, Node*>> s;
  for (int i = 0; i < (int)b.size(); i++) {
    if (i > 0) b[i]->l = b[i - 1];
    if (i < (int)b.size() - 1) b[i]->r = b[i + 1];
    s.insert({b[i]->val, b[i]});
  }
  int64_t ans = 0;
  for (int i = 0; i < m; i++) {
    debug(i);
    debug(s);
    auto it = prev(s.end());
    ans += it->first;
    cout << ans << " \n"[i == m - 1];
    auto x = it->second;
    vector<Node*> t(2 * k - 1, nullptr);
    t[k - 1] = x;
    for (int j = k - 1; j >= 0; j--) {
      if (t[j + 1]) t[j] = t[j + 1]->l;
    }
    for (int j = k - 1; j < 2 * k - 1; j++) {
      if (t[j - 1]) t[j] = t[j - 1]->r;
    }
    for (int j = 0; j < 2 * k - 1; j++) {
      if (t[j]) s.erase({t[j]->val, t[j]});
    }
    vector<Node*> new_nodes;
    for (int j = 0; j < k - 1; j++) {
      if (t[j] && t[j + k]) {
        auto new_node = new Node(t[j]->val + t[j + k]->val - x->val);
        new_nodes.push_back(new_node);
      }
    }
    if (new_nodes.empty()) {
      if (t[0] && t[0]->l) t[0]->l->r = nullptr;
      if (t.back() && t.back()->r) t.back()->r->l = nullptr;
    }
    for (int j = 0; j < (int)new_nodes.size(); j++) {
      if (j > 0) new_nodes[j]->l = new_nodes[j - 1];
      if (j < (int)new_nodes.size() - 1) new_nodes[j]->r = new_nodes[j + 1];
      s.insert({new_nodes[j]->val, new_nodes[j]});
    }
    if (t[0] && t[0]->l && !new_nodes.empty()) {
      t[0]->l->r = new_nodes[0];
      new_nodes[0]->l = t[0]->l;
    }
    if (t.back() && t.back()->r && !new_nodes.empty()) {
      t.back()->r->l = new_nodes.back();
      new_nodes.back()->r = t.back()->r;
    }
  }

  return 0;
}

Submission Info

Judge Result