제출 #220110

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
220110		rama_pang	Cake 3 (JOI19_cake3)	C++14	24 / 100	4081 ms	105996 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());

namespace Treap {
  struct Node {
    int prior, sz;
    int value;
    long long sum;
    Node *l = NULL, *r = NULL;

    Node() : prior(rnd()), sz(1), value(0), sum(0) {}
    Node(int v) : prior(rnd()), sz(1), value(v), sum(v) {}
  };

  using pt = Node*;

  const int LIM = 5e7;
  int new_node = 0;
  pt nodes[LIM];

  pt NewNode(int v) {
    return nodes[new_node++] = new Node(v);
  }

  int sz(pt t) { return t ? t->sz : 0; }
  long long sum(pt t) { return t ? t->sum : 0; }

  void pull(pt t) {
    if (t) {
      t->sum = sum(t->l) + sum(t->r) + t->value;
      t->sz = sz(t->l) + sz(t->r) + 1;
    }
  }

  void split_sz(pt t, pt &l, pt &r, int key) { // sz(l) = key
    if (!t) return void(l = r = NULL);
    int id = sz(t->l) + 1;
    if (id <= key) {
      split_sz(t->r, t->r, r, key - id), l = t;
    } else {
      split_sz(t->l, l, t->l, key), r = t;
    }
    pull(t);
  }

  void split_val(pt t, pt &l, pt &r, int key) { // val(l) <= key
    if (!t) return void(l = r = NULL);
    if (t->value <= key) {
      split_val(t->r, t->r, r, key), l = t;
    } else {
      split_val(t->l, l, t->l, key), r = t;
    }
    pull(t);
  }

  void merge(pt &t, pt l, pt r) {
    if (!l || !r) {
      t = l ? l : r;
    } else if (l->prior > r->prior) {
      merge(l->r, l->r, r), t = l;
    } else {
      merge(r->l, l, r->l), t = r;
    }
    pull(t);
  }

  void erase(pt &t, int key) {
    if (!t) return;
    if (t->value == key) {
      merge(t, t->l, t->r);
    } else if (t->value < key) {
      erase(t->r, key);
    } else {
      erase(t->l, key);
    }
    pull(t);
  }

  void insert(pt &t, int x) { // insert value x to the treap
    pt l, r;
    split_val(t, l, r, x);
    merge(l, l, NewNode(x));
    merge(t, l, r);
  }

  long long query(pt &t, int k) { // sum of k largest in treap
    pt l, r;
    int key = sz(t) - k;
    split_sz(t, l, r, key);
    long long res = sum(r);
    merge(t, l, r);
    return res;
  }
}

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

int N, M;
vector<Cake> cake;
Treap::Node *treap = NULL;

long long Query(int l, int r) {
  if (r - l + 1 < M) return -INF;
  static int tl = 0, tr = -1;
  while (tr < r) Treap::insert(treap, cake[++tr].V);
  while (tl > l) Treap::insert(treap, cake[--tl].V);
  while (tr > r) Treap::erase(treap, cake[tr--].V);
  while (tl < l) Treap::erase(treap, cake[tl++].V);
  return Treap::query(treap, M) - 2 * (cake[r].C - cake[l].C);
}

long long Solve(int L1, int L2, int R1, int R2) {
  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)});
}

int main() {
  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); 
  });

  cout << Solve(0, N - M, 0, N - 1) << "\n";
  return 0;
}

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