Submission #538832

#	Time	Username	Problem	Language	Result	Execution time	Memory
538832		czhang2718	Cake 3 (JOI19_cake3)	C++17	100 / 100	3638 ms	14376 KiB

cake3

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

#define rep(i,a,b) for(int i=a; i<=b; i++)
typedef vector<int> vi;
#define pb push_back
#define f first
#define s second
typedef long long ll;

const int N=200000;
int n,M;
int V[N], C[N];
int ind[N];
ll ans=-1e18;

int cnt[4*N];
ll sum[4*N];

void upd(int i, int v, int x=0, int lx=0, int rx=n){
  if(rx-lx==1){
    cnt[x]=(v!=0);
    sum[x]=v;
    return;
  }
  int m=(lx+rx)/2;
  if(i<m) upd(i, v, 2*x+1, lx, m);
  else upd(i, v, 2*x+2, m, rx);
  cnt[x]=cnt[2*x+1]+cnt[2*x+2];
  sum[x]=sum[2*x+1]+sum[2*x+2];
}

ll walk(int k, int x=0, int lx=0, int rx=n){
  if(k<=0) return 0;
  if(rx-lx==1) return sum[x]; // why needed
  int m=(lx+rx)/2;
  if(cnt[2*x+2]<=k) return sum[2*x+2]+walk(k-cnt[2*x+2], 2*x+1, lx ,m);
  return walk(k, 2*x+2, m, rx);
}

void solve(int l, int r, int a, int b){ // [l, r) [a, b]
  if(r<=l || b<a) return;
  int m=(l+r)/2;
  // if(a>=m-(M-2)) return solve(m+1, r, a, b);
  pair<ll, int> opt={-1e18, 0}; 
  for(int i=m-1; i>=max(l, b+1); i--) upd(ind[i], V[i]);
  for(int i=min(m-1, b); i>=a; i--){
    if(m-i+1>=M) opt=max(opt, {walk(M-2)+V[m]+V[i]+2*C[i]-2*C[m], i});
    upd(ind[i], V[i]);
  }
  ans=max(ans, opt.f);
  // cout << "opt " << m << " " << opt.s << " " << opt.f << "\n";
  for(int i=m-1; i>=max(l, b+1); i--) upd(ind[i], 0);
  for(int i=min(m-1, b); i>=a; i--) upd(ind[i], 0);

  for(int i=opt.s+1; i<=b; i++) if(i<l) upd(ind[i], V[i]);
  solve(l, m, a, opt.s);

  for(int i=opt.s+1; i<=b; i++) if(i<l) upd(ind[i], 0);
  for(int i=max(b+1, l); i<=m; i++) upd(ind[i], V[i]);
  solve(m+1, r, opt.s, b);

  for(int i=max(b+1, l); i<=m; i++) upd(ind[i], 0);
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> M;
  vector<pair<int, int>> vec;
  rep(i,0,n-1){
    int v,c; cin >> v >> c;
    vec.push_back({c, v});
  }
  sort(vec.begin(), vec.end());

  rep(i,0,n-1) V[i]=vec[i].second, C[i]=vec[i].first;

  vec.clear();
  rep(i,0,n-1) vec.push_back({V[i], i});
  sort(vec.begin(), vec.end());
  rep(i,0,n-1) ind[vec[i].s]=i;

  solve(0, n, 0, n-1);

  cout << ans;
}

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