Submission #1173752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173752		Hanksburger	Cake 3 (JOI19_cake3)	C++20	100 / 100	2571 ms	17648 KiB

cake3

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define ordered_set tree<pair<int, int>, null_type, greater<pair<int, int> >, rb_tree_tag, tree_order_statistics_node_update>
int ans[200005], n, m, l=-1, r=-1, sum, ANS=-1e18;
vector<pair<int, int> > vec;
ordered_set s;
void add(int i)
{
    s.insert({vec[i].second, i});
    int ind=s.order_of_key({vec[i].second, i});
    if (ind<m)
    {
        sum+=vec[i].second;
        if (s.size()>m)
            sum-=s.find_by_order(m)->first;
    }
    //cout << "add " << i << ' ' << sum << '\n';
}
void remove(int i)
{
    s.erase({vec[i].second, i});
    int ind=s.order_of_key({vec[i].second, i});
    if (ind<m)
    {
        sum-=vec[i].second;
        if (s.size()>=m)
            sum+=s.find_by_order(m-1)->first;
    }
    //cout << "remove " << i << ' ' << sum << '\n';
}
void adjust(int ql, int qr)
{
    //cout << "adjust " << l << ' ' << r << ' ' << ql << ' ' << qr << '\n';
    if (r<ql || qr<l)
    {
        //cout << "reset " << ql << ' ' << qr << '\n';
        l=ql, r=qr, sum=0, s.clear();
        for (int i=l; i<=r; i++)
            add(i);
        return;
    }
    for (int i=l; i<ql; i++)
        remove(i);
    for (int i=ql; i<l; i++)
        add(i);
    for (int i=r+1; i<=qr; i++)
        add(i);
    for (int i=qr+1; i<=r; i++)
        remove(i);
    l=ql, r=qr;
}
void recur(int xl, int xr, int yl, int yr)
{
    //cout << "recur " << xl << ' ' << xr << ' ' << yl << ' ' << yr << '\n';
    int xmid=(xl+xr)/2, ind;
    //if (xl==18 && xr==18)
    //    cout << "adjust " << l << ' ' << r << ' ' << xmid+1 << ' ' << max(xmid+1, yl-1) << '\n';
    adjust(xmid+1, max(xmid+m, yl-1));
    //if (xl==18 && xr==18)
    //    cout << "sum " << sum << '\n';
    //if (xl==18 && xr==18)
    //    cout << vec[18].first << ' ' << vec[18].second << '\n';
    for (int i=max(xmid+m+1, yl); i<=yr; i++)
    {
        if (ans[xmid]<sum+vec[i].second-vec[i].first*2)
        {
            ans[xmid]=sum+vec[i].second-vec[i].first*2;
            ind=i;
        }
        //cout << sum+vec[i].second-vec[i].first*2 << " -> " << xmid << ' ' << ans[xmid] << '\n';
        add(i);
        r++;

    }
    if (xl<xmid)
        recur(xl, xmid-1, yl, ind);
    if (xmid<xr)
        recur(xmid+1, xr, ind, yr);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    m-=2;
    for (int i=0; i<n; i++)
    {
        int v, c;
        cin >> v >> c;
        vec.push_back({c, v});
    }
    sort(vec.begin(), vec.end());
    for (int i=0; i<n; i++)
        ans[i]=-1e18;
    recur(0, n-m-2, m+1, n-1);
    for (int i=0; i<n; i++)
        ANS=max(ANS, ans[i]+vec[i].second+vec[i].first*2);
    //for (int i=0; i<n; i++)
    //    cout << ans[i]+vec[i].second+vec[i].first*2 << ' ';
    //cout << '\n';
    cout << ANS;
}

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