Submission #1037094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037094		juicy	Cake 3 (JOI19_cake3)	C++17	100 / 100	984 ms	15668 KiB

cake3

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5;
const long long inf = 1e18;

int n, m, sz;
int cnt[4 * N];
long long s[4 * N];
array<int, 2> a[N];
vector<int> comp;

void upd(int i, int x, int id = 1, int l = 1, int r = sz) {
  if (l == r) {
    s[id] += x;
    cnt[id] += x > 0 ? 1 : -1;
    return;
  }
  int md = (l + r) / 2;
  if (i <= md) {
    upd(i, x, id * 2, l, md);
  } else {
    upd(i, x, id * 2 + 1, md + 1, r);
  }
  s[id] = s[id * 2] + s[id * 2 + 1];
  cnt[id] = cnt[id * 2] + cnt[id * 2 + 1];
} 

long long qry(int k, int id = 1, int l = 1, int r = sz) {
  if (l == r) {
    long long value = s[id] / cnt[id];
    return value * k;
  }
  int md = (l + r) / 2;
  if (k > cnt[id * 2 + 1]) {
    return qry(k - cnt[id * 2 + 1], id * 2, l, md) + s[id * 2 + 1];
  }
  return qry(k, id * 2 + 1, md + 1, r);
}

void add(int i, int x) {
  upd(a[i][0], x * comp[a[i][0] - 1]);
}

int L = 1, R = 0;

void shift(int a, int b) {
  while (R < b) {
    add(++R, 1);
  }
  while (L > a) {
    add(--L, 1);
  }
  while (R > b) {
    add(R--, -1);
  }  
  while (L < a) {
    add(L++, -1);
  }
}

long long res = -inf;

void dc(int l, int r, int tl, int tr) {
  if (l > r) {
    return;
  }
  int md = (l + r) / 2;
  pair<long long, int> best = {-inf, -1};
  for (int i = tl; i <= min(tr, md - m + 1); ++i) {
    shift(i, md);
    best = max(best, {qry(m) - (long long) 2 * (a[md][1] - a[i][1]), i});
  }
  res = max(res, best.first);
  dc(l, md - 1, tl, best.second);
  dc(md + 1, r, best.second, tr);
}

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

  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i][0] >> a[i][1];
    comp.push_back(a[i][0]);
  }
  sort(a + 1, a + n + 1, [&](auto u, auto v) {
    return u[1] < v[1];
  });
  sort(comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());
  sz = comp.size();
  for (int i = 1; i <= n; ++i) {
    a[i][0] = lower_bound(comp.begin(), comp.end(), a[i][0]) - comp.begin() + 1;
  }
  dc(m, n, 1, n - m + 1);
  cout << res;
  return 0;
}

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