Submission #366397

#	Time	Username	Problem	Language	Result	Execution time	Memory
366397		Kazalika	Cake 3 (JOI19_cake3)	C++14	100 / 100	2625 ms	35932 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const int N = 2e5 + 5;
 
ll cval[N];
 
struct segment_tree {
  int size;
  vector<ll> sum, cnt;
  segment_tree() {}
  segment_tree(int sz) {
    size = sz;
    sum.resize(4 * size);
    cnt.resize(4 * size);
  }
  void upd(int t, int l, int r, int id, ll add) {
    if (l + 1 == r) {
      cnt[t] += add;
      sum[t] += add * cval[id];
      return;
    }
    int md = r + l >> 1;
    if (md > id)
      upd(t * 2 + 1, l, md, id, add);
    else
      upd(t * 2 + 2, md, r, id, add);
    sum[t] = sum[t * 2 + 1] + sum[t * 2 + 2];
    cnt[t] = cnt[t * 2 + 1] + cnt[t * 2 + 2];
  }
  void upd(int id, ll add) {
    upd(0, 0, size, id, add);
  }
  ll get(int t, int l, int r, ll k) {
    if (!k)
      return 0;
    if (l + 1 == r)
      return cval[l] * min(k, cnt[t]);
    int md = r + l >> 1;
    if (cnt[t * 2 + 1] >= k)
      return get(t * 2 + 1, l, md, k);
    return sum[t * 2 + 1] + get(t * 2 + 2, md, r, k - cnt[t * 2 + 1]);
  }
  ll get(ll k) {
    return get(0, 0, size, k);
  }
};
 
segment_tree sgt(N);
 
int n, m;
pair<ll, ll> vc[N];
vector<ll> vf;
 
const ll inf = 1e15;
 
ll ans[N];
 
int L, R = -1;
 
void add(int id) {
  sgt.upd(vc[id].first, 1);
}
void del(int id) {
  sgt.upd(vc[id].first, -1);
}
 
void move(int l, int r) {
  while (R < r) {
    R++;
    add(R);
  }
  while (L > l) {
    L--;
    add(L);
  }
  while (R > r) {
    del(R);
    R--;
  }
  while (L < l) {
    del(L);
    L++;
  }
}
 
void dc(int l, int r, int optl, int optr) {
  if (l > r)
    return;
  int md = l + r >> 1, opt = -1;
  ll mx = -inf;
  for (int p = max(optl, md + m - 1); p <= optr; ++p) {
    move(md, p);
    ll vl = sgt.get(m) - 2 * (vc[p].second - vc[md].second);
    if (vl > mx) {
      opt = p;
      mx = vl;
    }
  }
  assert(opt != -1);
  ans[md] = mx;
  dc(l, md - 1, optl, opt);
  dc(md + 1, r, opt, optr);
}
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  vf.resize(n);
  for (int i = 0; i < n; ++i) {
    cin >> vc[i].first >> vc[i].second;
    vf[i] = vc[i].first;
  }
  sort(vc, vc + n, [&](pair<ll, ll> a, pair<ll, ll> b) { return a.second < b.second; });
  sort(vf.begin(), vf.end());
  vf.erase(unique(vf.begin(), vf.end()), vf.end());
  sort(vf.rbegin(), vf.rend());
  map<ll, ll> proper;
  for (int i = 0; i < vf.size(); ++i) {
    proper[vf[i]] = i;
    cval[i] = vf[i];
  }
  for (int i = 0; i < n; ++i)
    vc[i].first = proper[vc[i].first];
  dc(0, n - m, 0, n - 1);
  ll res = -inf;
  for (int i = 0; i <= n - m; ++i)
    res = max(res, ans[i]);
  cout << res;
}

Compilation message (stderr)

cake3.cpp: In member function 'void segment_tree::upd(int, int, int, int, ll)':
cake3.cpp:25:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int md = r + l >> 1;
      |              ~~^~~
cake3.cpp: In member function 'll segment_tree::get(int, int, int, ll)':
cake3.cpp:41:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |     int md = r + l >> 1;
      |              ~~^~~
cake3.cpp: In function 'void dc(int, int, int, int)':
cake3.cpp:92:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   92 |   int md = l + r >> 1, opt = -1;
      |            ~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:122:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   for (int i = 0; i < vf.size(); ++i) {
      |                   ~~^~~~~~~~~~~

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