Submission #634798

#	Time	Username	Problem	Language	Result	Execution time	Memory
634798		tamthegod	Cake 3 (JOI19_cake3)	C++14	100 / 100	485 ms	151856 KiB

cake3

#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 2e5 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
vector<int> a;
vector <int> val[maxN * 4];
vector <int> sum[maxN * 4];
int node_cnt = 1;

struct TNode
{
    int l, r;
    int lp, rp;
    TNode()
    {
        l = r = lp = rp = 0;
    }
    TNode(int _l, int _r)
    {
        l = _l;
        r = _r;
    }
};
TNode wt[maxN * 4];

void build(int id, auto i, auto j, int l, int r)
{
    wt[id].l = l;
    wt[id].r = r;
    if (l == r)
    {
        return;
    }
    val[id].pb(0);
    sum[id].pb(0);
    int mid = (l + r - (l + r < 0)) / 2;
    int _max = l;
    int _min = r;
    for(auto it = i; it != j; ++it)
    {
        val[id].pb(val[id].back() + (*it <= mid));
        sum[id].pb(sum[id].back() + *it * (*it <= mid));
        if (*it <= mid) _max = max(_max, *it);
        else _min = min(_min, *it);
    }
    auto p = stable_partition(i, j,[=](const auto &w)
    {
        return w <= mid;
    });
    wt[id].lp = ++node_cnt;
    wt[id].rp = ++node_cnt;
    build(wt[id].lp, i, p, l, _max);
    build(wt[id].rp, p, j, _min, r);
}

ll get(int k, int i, int j)
{
    if (k == 0) return 0;
    if(j - i + 1 < k) return -oo;
    --i;
    ll res = 0;
    int id = 1;
    int l = wt[id].l, r = wt[id].r;
    while (l < r)
    {
        int mid = (l + r) / 2;
        if (k <= val[id][j] - val[id][i])
        {
            i = val[id][i];
            j = val[id][j];
            id = wt[id].lp;
        }
        else
        {
            res += sum[id][j] - sum[id][i];
            k -= val[id][j] - val[id][i];
            i -= val[id][i];
            j -= val[id][j];
            id = wt[id].rp;
        }
        l = wt[id].l, r = wt[id].r;
    }
    res += k * l;
    return res;
}

int n, m;
pair<int, int> cake[maxN];
int f[maxN];
void ReadInput()
{
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> cake[i].fi >> cake[i].se;
}
void DnC(int l, int r, int optl, int optr)
{
    if(l > r) return;
    int mid = (l + r) / 2;
    int res = -oo, id = -1;
    for(int i=optl; i<=min(optr, mid - m + 1); i++)
    {
        int val = cake[mid].fi + cake[i].fi + -get(m - 2, i + 1, mid - 1) - (cake[mid].se - cake[i].se) * 2;
        if(res < val)
        {
            res = val;
            id = i;
        }
    }
    f[mid] = res;
    DnC(l, mid - 1, optl, id);
    DnC(mid + 1, r, id, optr);
}
void Solve()
{
    sort(cake + 1, cake + n + 1, [](pair<int, int> p, pair<int, int> q)
    {
        return p.se < q.se;
    });
    a.resize(n + 1);
    for(int i=1; i<=n; i++) a[i] = -cake[i].fi;
    build(1, a.begin() + 1, a.end(), *min_element(a.begin() + 1, a.end()), *max_element(a.begin() + 1, a.end()));
    DnC(m, n, 1, n - m + 1);
    cout << *max_element(f + m, f + n + 1);
}
int32_t main()
{
   // freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Compilation message (stderr)

cake3.cpp:36:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   36 | void build(int id, auto i, auto j, int l, int r)
      |                    ^~~~
cake3.cpp:36:28: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   36 | void build(int id, auto i, auto j, int l, int r)
      |                            ^~~~
cake3.cpp: In function 'll get(long long int, long long int, long long int)':
cake3.cpp:76:13: warning: unused variable 'mid' [-Wunused-variable]
   76 |         int mid = (l + r) / 2;
      |             ^~~

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