Submission #1257416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257416		chikien2009	Cake 3 (JOI19_cake3)	C++20	100 / 100	458 ms	6772 KiB

cake3

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

struct FENWICK_TREE
{
    long long val[200001];
    int num[200001];
    inline void Add(int x, int v)
    {
        while (x <= 2e5)
        {
            val[x] += v;
            num[x]++;
            x += (x & (~(x - 1)));
        }
    }
    inline void Remove(int x, int v)
    {
        while (x <= 2e5)
        {
            val[x] -= v;
            num[x]--;
            x += (x & (~(x - 1)));
        }
    }
    inline long long Get(int x)
    {
        long long res = 0, p = 0;
        for (int i = 19; i >= 0; --i)
        {
            if (p + (1 << i) <= 2e5 && num[p + (1 << i)] <= x)
            {
                p += (1 << i);
                res += val[p];
                x -= num[p];
            }
        }
        return (x > 0 ? -1e18 : res);
    }
} ft;

int n, m;
array<int, 3> a[200000];
long long f[200000];

inline bool Comp(const array<int, 3> &ina, const array<int, 3> &inb)
{
    return ina[1] < inb[1];
}

// Fenwick tree store data from lp to r

inline void Move(int l, int r, int nl, int nr)
{
    while (l < nl)
    {
        ft.Remove(a[l][2], a[l][0]);
        l++;
    }
    while (nl < l)
    {
        l--;
        ft.Add(a[l][2], a[l][0]);
    }
    while (nr < r)
    {
        ft.Remove(a[r][2], a[r][0]);
        r--;
    }
    while (r < nr)
    {
        r++;
        ft.Add(a[r][2], a[r][0]);
    }
}

inline void Form(int l, int r, int lp, int rp)
{
    int opt = lp, mid = (l + r) >> 1, p = min(mid - m + 1, rp);
    Move(lp, r, lp, mid);
    for (int i = lp; i <= p; ++i)
    {
        if (f[mid] < ft.Get(m) - 2 * (a[mid][1] - a[i][1]))
        {
            f[mid] = ft.Get(m) - 2 * (a[mid][1] - a[i][1]);
            opt = i;
        }
        Move(i, mid, i + 1, mid);
    }
    Move(p + 1, mid, lp, mid - 1);
    if (l <= mid - 1)
    {
        Form(l, mid - 1, lp, opt);
    }
    Move(lp, mid - 1, opt, r);
    if (mid + 1 <= r)
    {
        Form(mid + 1, r, opt, rp);
    }
    Move(opt, r, lp, r);
}

int main()
{
    setup();

    cin >> n >> m;
    fill_n(f, n, -1e18);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i][0] >> a[i][1];
    }
    sort(a, a + n, greater<array<int, 3>>());
    for (int i = 0; i < n; ++i)
    {
        a[i][2] = i + 1;
        ft.Add(a[i][2], a[i][0]);
    }
    sort(a, a + n, Comp);
    Form(m - 1, n - 1, 0, n - m);
    cout << (*max_element(f, f + n));
    return 0;
}

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