Submission #1090761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1090761		epicci23	Cake 3 (JOI19_cake3)	C++17	100 / 100	1000 ms	215632 KiB

cake3

#include "bits/stdc++.h"
#define int long long
#define all(v) v.begin() , v.end()
#define sz(a) (int)a.size()
using namespace std;

const int INF = 1e18;
const int N = 2e5 + 5;
struct Node{
  Node* lc;
  Node* rc;
  int cnt, sub;
  Node(){
    lc = rc = NULL;
    cnt = sub = 0;
  }
};

struct PST{
  int n, def;
  vector<Node*> roots;

  Node* build(int l, int r){
    if(l == r) return new Node();
    int m = (l + r) / 2;
    Node* res = new Node();
    res -> lc = build(l, m);
    res -> rc = build(m + 1, r);
    return res;
  }

  Node* update(Node* rt, int l, int r, int ind, int u){
    if(l == r){
      Node* res = new Node();
      res -> sub = rt -> sub + 1;
      res -> cnt = rt -> cnt + u;
      return res;
    }
    Node* res = new Node();
    int m = (l + r) / 2;
    if(ind <= m){
      res -> lc = update(rt -> lc, l, m, ind, u);
      res -> rc = rt -> rc;
    }
    else{
      res -> lc = rt -> lc;
      res -> rc = update(rt -> rc, m + 1, r, ind, u);
    }
    res -> sub = res -> lc -> sub + res -> rc -> sub;
    res -> cnt = res -> lc -> cnt + res -> rc -> cnt;
    return res;
  }

  PST(int _n, int _def){
    n = _n, def = _def;
    roots.push_back(build(1, n));
  }

  void add_index(int ind, int u){
    roots.push_back(update(roots.back(), 1, n, ind, u));
  }

  int get_sum(int l, int r, int k){
    Node* pl = roots[l - 1];
    Node* pr = roots[r];
    int res = 0;

    while(pl -> lc != NULL){
     if((pr -> rc -> sub) - (pl -> rc -> sub) >= k){
       pr = pr -> rc;
       pl = pl -> rc;
     }
     else{
       res += (pr -> rc -> cnt) - (pl -> rc -> cnt);
       k -= (pr -> rc -> sub) - (pl -> rc -> sub);
       pr = pr -> lc;
       pl = pl -> lc; 
     }
    }

    if(k) res += k * ((pr -> cnt - pl -> cnt) / (pr -> sub - pl -> sub));
    
    return res;
  }
};

int n, k, ans = -INF;
map<int,int> mp;
array<int,2> v[N];
PST pst = PST(1,1);

void calc(int l, int r, int optl, int optr){
  if(l > r) return;
  int m = (l + r) / 2;
  int res = -INF, opt  = -1;
  for(int i = max(optl, m + k - 1); i <= optr; i++){
    if(v[m][1] + v[i][1] +  v[m][0] - v[i][0] + pst.get_sum(m + 1, i - 1, k - 2) > res){
      res = v[m][1] + v[i][1] + v[m][0] - v[i][0] + pst.get_sum(m + 1, i - 1, k - 2);
      opt = i;
    }
  }
  ans = max(ans, res);
  calc(l, m - 1, optl, opt), calc(m + 1, r, opt, optr);
}

void _(){
  cin >> n >> k;
  
  for(int i=1;i<=n;i++){
    int a, b;
    cin >> a >> b;
    v[i] = {2 * b, a};
    mp[a] = 1;
  }

  int p=0;
  for(auto x:mp) mp[x.first]=++p;
   
  sort(v+1,v+n+1);
  pst = PST(n,0);
  
  for(int i=1;i<=n;i++) pst.add_index(mp[v[i][1]], v[i][1]);

  calc(1, n - k + 1, 1, n);

  cout << ans << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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