Submission #842368

#	Time	Username	Problem	Language	Result	Execution time	Memory
842368		Dec0Dedd	Cake 3 (JOI19_cake3)	C++14	100 / 100	1081 ms	222364 KiB

cake3

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

const int N = 2e5+10;
const ll INF = 1e18;

struct Vertex {
    Vertex *l, *r;
    pii val;

    Vertex(pii x) : l(nullptr), r(nullptr), val(x) {}
    Vertex(Vertex *l, Vertex *r) : l(l), r(r), val({0, 0}) {
        if (l) val.first+=l->val.first, val.second+=l->val.second;
        if (r) val.first+=r->val.first, val.second+=r->val.second;
    }
};

Vertex* build(int l, int r) {
    if (l == r) return new Vertex(make_pair(0, 0));
    int m=(l+r)/2;
    return new Vertex(build(l, m), build(m+1, r));
}

Vertex* upd(Vertex* v, int l, int r, int p, ll nvl) {
    if (l == r) {
        return new Vertex(make_pair(v->val.first+nvl, v->val.second+1));
    } int m=(l+r)/2;
    if (p <= m) return new Vertex(upd(v->l, l, m, p, nvl), v->r);
    return new Vertex(v->l, upd(v->r, m+1, r, p, nvl)); 
}

ll que(Vertex* vl, Vertex *vr, int l, int r, int x) {
    if (l == r) {
        ll k=vr->val.second-vl->val.second, sm=vr->val.first-vl->val.first;
        assert(k >= x);
        return (sm/k)*x;
    }
    int m=(l+r)/2, rcnt=vr->r->val.second-vl->r->val.second;
    if (rcnt >= x) return que(vl->r, vr->r, m+1, r, x);
    return que(vl->l, vr->l, l, m, x-rcnt)+(vr->r->val.first-vl->r->val.first);
}

ll n, m, dp[N];
vector<pii> x;
set<int> st;
map<int, int> sc;

pii mx(pii a, pii b) {
    if (a.first > b.first) return a;
    if (b.first > a.first) return b;
    if (a.first == b.first) {
        if (a.second < b.second) return a;
        return b;
    }
}

vector<Vertex*> rts;

void solve(int l, int r, int opl, int opr) {
    if (l > r) return;
    int md=(l+r)/2;

    pii tmp={-INF, n};
    for (int i=max(1ll*opl, md+m-1); i<=opr; ++i) {
        assert(i-md+1 >= m);
        ll q=que(rts[md], rts[i-1], 1, n, m-2);
        tmp=mx(tmp, {q+x[i-1].second+x[md-1].second-2*abs(x[i-1].first-x[md-1].first), i});
    } dp[md]=tmp.first;
    solve(l, md-1, opl, tmp.second), solve(md+1, r, tmp.second, opr);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    cin>>n>>m;
    for (int i=1; i<=n; ++i) {
        ll v, c; cin>>v>>c;
        x.push_back({c, v}); st.insert(v);
    } sort(x.begin(), x.end());

    int i=1;
    for (auto u : st) sc[u]=i++;

    rts.push_back(build(1, n));
    for (int i=1; i<=n; ++i) {
        rts.push_back(upd(rts.back(), 1, n, sc[x[i-1].second], x[i-1].second));
    }
    solve(1, n-m+1, 1, n);

    ll ans=-INF;
    for (int i=1; i<=n-m+1; ++i) ans=max(ans, dp[i]);
    cout<<ans<<"\n";
}

Compilation message (stderr)

cake3.cpp: In function 'pii mx(pii, pii)':
cake3.cpp:59:1: warning: control reaches end of non-void function [-Wreturn-type]
   59 | }
      | ^

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