Submission #220111

#	Time	Username	Problem	Language	Result	Execution time	Memory
220111		rama_pang	Cake 3 (JOI19_cake3)	C++14	100 / 100	1761 ms	17004 KiB

cake3

#include <bits/stdc++.h>
using namespace std;

const long long INF = 1e18;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());

class SegmentTree {
 private:
  int sz;
  vector<int> A;
  vector<pair<long long, int>> tree;

  void Update(int n, int tl, int tr, int pos, int activate) {
    if (tl == tr) return void(tree[n] = {activate ? A[pos] : 0, activate});
    int mid = (tl + tr) / 2;
    int lc = n + 1;
    int rc = n + 2 * (mid - tl + 1);
    if (pos <= mid) {
      Update(lc, tl, mid, pos, activate);
    } else {
      Update(rc, mid + 1, tr, pos, activate);
    }
    tree[n] = {tree[lc].first + tree[rc].first, tree[lc].second + tree[rc].second};
  }

  long long Query(int n, int tl, int tr, int key) { // sum of key minimum elements
    if (key <= 0) return 0;
    if (tree[n].second <= key) return tree[n].first;
    int mid = (tl + tr) / 2;
    int lc = n + 1;
    int rc = n + 2 * (mid - tl + 1);
    return Query(lc, tl, mid, key) + Query(rc, mid + 1, tr, key - tree[lc].second);
  }

 public:
  SegmentTree() {}
  SegmentTree(int n, vector<int> A) : sz(n), A(A) {
    tree.resize(2 * sz);
  }

  void Insert(int pos) {
    return Update(1, 0, sz - 1, pos, 1);
  }

  void Erase(int pos) {
    return Update(1, 0, sz - 1, pos, 0);
  }

  long long Query(int key) { // return key largest elements
    return tree[1].first - Query(1, 0, sz - 1, tree[1].second - key);
  }
};

struct Cake {
  int V, C;
  Cake() {}
  Cake(int V, int C) : V(V), C(C) {}
};

int N, M;
vector<Cake> cake;

SegmentTree seg;
vector<int> coord;

void Init() { // coordinate compression on cake based on V, cakes initially sorted by C
  vector<pair<int, int>> all;
  for (int i = 0; i < N; i++) {
    all.emplace_back(cake[i].V, i);
  }
  sort(begin(all), end(all));
  
  coord.resize(N);
  for (int i = 0; i < N; i++) {
    coord[all[i].second] = i;
  }

  vector<int> A;
  for (int i = 0; i < N; i++) {
    A.emplace_back(all[i].first);
  }

  seg = SegmentTree(N, A);
}

long long Query(int l, int r) {
  if (r - l + 1 < M) return -INF;
  static int tl = 0, tr = -1;
  while (tr < r) seg.Insert(coord[++tr]);
  while (tl > l) seg.Insert(coord[--tl]);
  while (tr > r) seg.Erase(coord[tr--]);
  while (tl < l) seg.Erase(coord[tl++]);
  return seg.Query(M) - 2 * (cake[r].C - cake[l].C);
}

long long Solve(int L1 = 0, int L2 = N - M, int R1 = 0, int R2 = N - 1) {
  if (L1 > L2) return -INF;
  int L = (L1 + L2) / 2;
  int opt = -1;
  long long cur = -INF;
  for (int R = max(R1, L + M - 1); R <= R2; R++) {
    long long now = Query(L, R);
    if (now > cur) cur = now, opt = R;
  }
  return max({cur, Solve(L1, L - 1, R1, opt), Solve(L + 1, L2, opt, R2)});
}

void Read() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);

  cin >> N >> M;
  
  cake.resize(N);
  for (int i = 0; i < N; i++) {
    cin >> cake[i].V >> cake[i].C;
  }

  sort(begin(cake), end(cake), [&](const Cake &a, const Cake &b) { 
    return make_pair(a.C, a.V) < make_pair(b.C, b.V); 
  });
}

int main() {
  Read();
  Init();
  cout << Solve() << "\n";
  return 0;
}

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