제출 #1160453

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1160453		fryingduc	Cake 3 (JOI19_cake3)	C++20	100 / 100	2506 ms	8912 KiB

cake3

#include "bits/stdc++.h"

using namespace std;

#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif

const int maxn = 2e5 + 5;
int n, m;
pair<int, int> a[maxn];
int ord[maxn];

long long tree[maxn << 2];
int cnt[maxn << 2];
int lim;
long long res;
int L = 1, R;
vector<int> comp;

void update(int pos, int val, int ind = 1, int l = 1, int r = lim) {
  if (l == r) {
    tree[ind] += val;
    cnt[ind] += (val > 0 ? 1 : -1);
    return;
  }
  int mid = (l + r) >> 1;
  if (pos <= mid) {
    update(pos, val, ind << 1, l, mid);
  } else {
    update(pos, val, ind << 1 | 1, mid + 1, r);
  }
  tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
  cnt[ind] = cnt[ind << 1] + cnt[ind << 1 | 1];
}

long long walk(int k, int ind = 1, int l = 1, int r = lim) {
  if (l == r) {
    if (!cnt[ind]) return 0;
    return tree[ind] / cnt[ind] * k;
  }
  int mid = (l + r) >> 1;
  if (k >= cnt[ind << 1 | 1]) {
    return walk(k - cnt[ind << 1 | 1], ind << 1, l, mid) + tree[ind << 1 | 1];
  }
  return walk(k, ind << 1 | 1, mid + 1, r);
}

void upd(int id, int delta) {
  update(a[id].first, comp[a[id].first - 1] * delta);
}

long long cost(int l, int r) {
  while (R < r) upd(++R, 1);
  while (L > l) upd(--L, 1);
  while (R > r) upd(R--, -1);
  while (L < l) upd(L++, -1);

  upd(l, -1), upd(r, -1);
  long long cc = walk(m - 2) + comp[a[r].first - 1] + comp[a[l].first - 1];
  cc -= abs(a[r].second - a[l].second) * 2;
//  debug(l, r, cc, walk(m - 2));
  upd(l, 1), upd(r, 1);
  return cc;
}

void calc(int l, int r, int optl, int optr) {
  if (l > r) return;
  int mid = (l + r) >> 1;
  long long xx = -1e18;
  int opt = optl;
  for (int i = optl; i <= min(mid - m + 1, optr); ++i) {
    long long cur = cost(i, mid);
    if (cur > xx) {
      xx = cur;
      opt = i;
    } 
  }
  res = max(res, xx);
  calc(l, mid - 1, optl, opt);
  calc(mid + 1, r, opt, optr);
}

void solve() {
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i].first >> a[i].second;
    comp.push_back(a[i].first);
  }
  sort(comp.begin(), comp.end());
  comp.erase(unique(comp.begin(), comp.end()), comp.end());
  sort(a + 1, a + n + 1, [](const pair<int, int> &x, const pair<int, int> &y) -> bool {
    return (x.second != y.second ? x.second < y.second : x.first < y.first);
  });
  for (int i = 1; i <= n; ++i) {
//    debug(a[i]);
    a[i].first = lower_bound(comp.begin(), comp.end(), a[i].first) - comp.begin() + 1;
  }
  lim = (int)comp.size();
  res = -1e18;
  calc(m, n, 1, n - m + 1);
  cout << res;
}

signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  solve();

  return 0;
}

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