Submission #1172238

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172238		jill	Cake 3 (JOI19_cake3)	C++20	0 / 100	124 ms	219684 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
using ll = long long;
using pii = pair<ll, ll>;
const ll maxn = 4e6 + 5, inf = 1e9, oo = 1e18;
ll n, m, dp[2][maxn];
pii a[maxn];
struct WT
{
    struct node
    {
        int l, r;
        vector<ll> x;
        vector<ll> s;
    } t[maxn];

    int build(vector<ll> &seq, ll a = 0, ll b = inf)
    {
        static int idxNode = 0;
        if (seq.empty())
            return -1;

        int cur = idxNode++;
        if (a == b)
            return cur;
        t[cur].x.resize(seq.size());
        t[cur].s.resize(seq.size());
        ll mid = (a + b) / 2;
        vector<ll> left_seq, right_seq;
        for (int i = 0; i < (int)seq.size(); i++)
        {
            if (seq[i] <= mid)
            {
                left_seq.push_back(seq[i]);
            }
            else
            {
                t[cur].x[i] = 1;
                t[cur].s[i] = seq[i];
                right_seq.push_back(seq[i]);
            }
        }
        for (int i = (int)seq.size() - 2; i >= 0; i--)
        {
            t[cur].x[i] += t[cur].x[i + 1];
            t[cur].s[i] += t[cur].s[i + 1];
        }

        t[cur].l = build(left_seq, a, mid);
        t[cur].r = build(right_seq, mid + 1, b);

        return cur;
    }

    int map_left(int nd, int i)
    {
        return i >= 0 ? i - t[nd].x[i] : -1;
    }
    int map_right(int nd, int i)
    {
        return i >= 0 ? t[nd].x[i] - 1 : -1;
    }

    int countRight(int cur, int l, int r)
    {
        if (l > r)
            return 0;
        ll totalR = t[cur].x[l];
        ll beyond = (r + 1 < (int)t[cur].x.size()) ? t[cur].x[r + 1] : 0;
        return (int)(totalR - beyond);
    }

    int64_t sumRight(int cur, int l, int r)
    {
        if (l > r)
            return 0LL;
        ll totalR = t[cur].s[l];
        ll beyond = (r + 1 < (int)t[cur].s.size()) ? t[cur].s[r + 1] : 0LL;
        return (totalR - beyond);
    }
    ll queryUtil(int node, int a, int b, int l, int r, int k)
    {
        if (node == -1 || l > r || k <= 0)
            return 0LL;
        if (a == b)
        {
            int countSeg = (r - l + 1);
            int take = min(countSeg, k);
            return 1LL * take * a;
        }

        int mid = (a + b) >> 1;

        int totalR = countRight(node, l, r);
        if (totalR >= k)
        {
            int newL = map_right(node, l - 1) + 1;
            int newR = map_right(node, r);
            return queryUtil(t[node].r, mid + 1, b, newL, newR, k);
        }
        else
        {
            ll sumR = sumRight(node, l, r);
            int newL = map_left(node, l - 1) + 1;
            int newR = map_left(node, r);
            return sumR + queryUtil(t[node].l, a, mid, newL, newR, k - totalR);
        }
    }

    ll query(int l, int r, int k)
    {
        if (l > r)
            return 0LL;
        return queryUtil(0, 0, inf, l, r, k);
    }
} tree;
void calc(int x, int l, int r, int opl, int opr)
{
    if (l > r)
        return;
    int mid = l + r >> 1;
    pii best = {-oo, -1};
    for (int k = opl; k < min(mid, opr); k++)
    {
        best = max(best, {tree.query(k + 1, mid - 1, m - 2) + a[mid].fi + a[k].fi - 2 * abs(a[mid].se - a[k].se), k});
    }
    dp[x][mid] = best.fi;
    int opt = best.se;
    calc(x, l, mid - 1, opl, opt);
    calc(x, mid + 1, r, opt, opr);
}
vector<ll> b;
signed main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].fi >> a[i].se;
    }
    sort(a, a + n, [](auto x, auto y)
         { return x.se < y.se; });
    for (int i = 0; i < n; i++)
    {
        dp[0][i] = a[i].fi - a[i].se;
        b.push_back(a[i].fi);
    }
    tree.build(b);
    calc(1, 0, n - 1, 0, n - 1);
    cout << *max_element(dp[1], dp[1] + n);
    return 0;
}

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