Submission #1197220

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197220		avighna	Cake 3 (JOI19_cake3)	C++20	100 / 100	590 ms	107612 KiB

cake3

#include <bits/stdc++.h>

class WaveletTree {
private:
  std::vector<std::vector<int>> left;
  std::vector<std::vector<int64_t>> psum;
  std::vector<int> a;
  
public:
  std::vector<std::pair<int, int>> compress;
  std::vector<int> uncompressed;
  int n;

  WaveletTree(const std::vector<int> &_a) : a(_a), n(0) {
    compress.resize(_a.size());
    for (int i = 0; i < _a.size(); ++i) {
      compress[i] = {_a[i], i};
    }
    std::sort(compress.begin(), compress.end());
    std::vector<int> a(_a.size());
    uncompressed.resize(_a.size());
    for (int i = 0; i < _a.size(); ++i) {
      if (i != 0 and compress[i].first != compress[i - 1].first) {
        uncompressed[n++] = compress[i - 1].first;
      }
      a[compress[i].second] = n;
    }
    uncompressed[n++] = compress.back().first;

    left.resize(4 * n), psum.resize(4 * n);
    construct(1, 0, n - 1, a.begin(), a.end());
  }

  void construct(int v, int tl, int tr, std::vector<int>::iterator l,
                 std::vector<int>::iterator r) {
    left[v].resize(r - l + 1), psum[v].resize(r - l + 1);
    int tm = tl + (tr - tl) / 2;
    for (auto it = l; it != r; ++it) {
      left[v][it - l + 1] = left[v][it - l] + (*it <= tm);
      psum[v][it - l + 1] = psum[v][it - l] + uncompressed[*it];
    }
    if (tl != tr and l != r) {
      auto it = std::stable_partition(l, r, [&](int x) { return x <= tm; });
      construct(2 * v, tl, tm, l, it);
      construct(2 * v + 1, tm + 1, tr, it, r);
    }
  }

  int kth(int v, int tl, int tr, int l, int r, int k) {
    if (tl == tr) {
      return tl;
    }
    int tm = (tl + tr) / 2;
    int cnt = left[v][r] - left[v][l - 1];
    if (k <= cnt) {
      return kth(2 * v, tl, tm, left[v][l - 1] + 1, left[v][r], k);
    }
    return kth(2 * v + 1, tm + 1, tr, l - left[v][l - 1], r - left[v][r], k - cnt);
  }
  int kth(int l, int r, int k) {
    return kth(1, 0, n - 1, l + 1, r + 1, k);
  }

  std::pair<int64_t, int> sum(int v, int tl, int tr, int l, int r, int k) {
    if (k < tl) {
      return {0, 0};
    }
    if (tr <= k) {
      return {psum[v][r] - psum[v][l - 1], r - l + 1};
    }
    int tm = (tl + tr) / 2;
    auto [s1, c1] = sum(2 * v, tl, tm, left[v][l - 1] + 1, left[v][r], k);
    auto [s2, c2] = sum(2 * v + 1, tm + 1, tr, l - left[v][l - 1], r - left[v][r], k);
    return {s1 + s2, c1 + c2};
  }
  std::pair<int64_t, int> sum(int l, int r, int k) {
    return sum(1, 0, n - 1, l + 1, r + 1, k);
  }
};

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

  const int64_t inf = 1e15;

  int n, m;
  std::cin >> n >> m;
  std::vector<std::pair<int64_t, int64_t>> a(n);
  for (auto &[c, v] : a) {
    std::cin >> v >> c;
    c <<= 1;
  }
  std::sort(a.begin(), a.end());

  int64_t ans = -inf;
  std::vector<int> b(n);
  for (int i = 0; i < n; ++i) {
    b[i] = -a[i].second;
  }
  WaveletTree wv(b);
  auto solve = [&](auto &&self, int tl, int tr, int l, int r) -> void {
    if (tl > tr) {
      return;
    }
    int tm = (tl + tr) / 2;
    std::pair<int64_t, int> opt = {-inf, -1};
    for (int i = l; i <= r; ++i) {
      if (i - 1 - (tm + 1) + 1 < m - 2) {
        continue;
      }
      int val = wv.kth(tm + 1, i - 1, m - 2);
      auto [sum, cnt] = wv.sum(tm + 1, i - 1, val - 1);
      sum += (m - 2 - cnt) * wv.uncompressed[val];
      sum = -sum;
      opt = std::max(opt, {a[tm].second + sum + a[i].second - (a[i].first - a[tm].first), i});
    }
    ans = std::max(ans, opt.first);
    self(self, tl, tm - 1, l, opt.second);
    self(self, tm + 1, tr, opt.second, r);
  };
  solve(solve, 0, n - m, 0, n - 1);
  std::cout << ans << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76