Submission #923628

#	Time	Username	Problem	Language	Result	Execution time	Memory
923628		danikoynov	Cake 3 (JOI19_cake3)	C++14	100 / 100	1158 ms	19236 KiB

cake3

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 2e5 + 10;

struct element
{
    ll v, s, idx;

    element(ll _v = 0, ll _s = 0, ll _idx = 0)
    {
        v = _v;
        s = _s;
        idx = _idx;
    }
} e[maxn];
int n, m;

void input()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        cin >> e[i].v >> e[i].s;
        e[i].s *= 2;
        e[i].idx = i;
    }
}

bool cmp_second(element e1, element e2)
{
    return e1.s < e2.s;
}
ll inf = 1e18;


ll result;

ll dp[maxn];

int lb = 1, rb = 0;
int tree[4 * maxn];

void update(int root, int left, int right, int pos, int val)
{
    if (left == right)
    {
        tree[root] = val;
        return;
    }

    int mid = (left + right) / 2;
    if (pos <= mid)
        update(root * 2, left, mid, pos, val);
    else
        update(root * 2 + 1, mid + 1, right, pos, val);

    tree[root] = tree[root * 2] + tree[root * 2 + 1];
}

int walk(int root, int left, int right, int take)
{
    if (left == right)
        return left;

    int mid = (left + right) / 2;
    if (tree[root * 2 + 1] >= take)
        return walk(root * 2 + 1, mid + 1, right, take);
    else
        return walk(root * 2, left, mid, take - tree[root * 2 + 1]);
}

int rev[maxn];
ll num[maxn];

ll fen[maxn];
void point_add(int pos, ll v)
{
    for (int i = pos; i <= n; i += (i & -i))
        fen[i] += v;
}

ll fen_sum(int pos)
{
    ll s = 0;
    for (int i = pos; i > 0; i -= (i & -i))
        s += fen[i];
    return s;
}

ll range_sum(int l, int r)
{
    return fen_sum(r) - fen_sum(l - 1);
}
ll cost(int left, int right)
{
    ///cout << "cost" << endl;
    while(rb < right)
    {
        rb ++;
        update(1, 1, n, rev[rb], 1);
        point_add(rev[rb], num[rev[rb]]);
    }

    while(lb > left)
    {
        lb --;
        update(1, 1, n, rev[lb], 1);
        point_add(rev[lb], num[rev[lb]]);
    }

    while(rb > right)
    {
        update(1, 1, n, rev[rb], 0);
        point_add(rev[rb], -num[rev[rb]]);
        rb --;
    }
    ///cout << "fine" << endl;
    while(lb < left)
    {
        update(1, 1, n, rev[lb], 0);
        point_add(rev[lb], -num[rev[lb]]);
        lb ++;
    }

    int pivot = walk(1, 1, n, m);
    return range_sum(pivot, n);

    //cout << "cost " << left << " " << right << endl;
    /**vector < ll > values;
    for (int i = left; i <= right; i ++)
        values.push_back(e[i].v);

    sort(values.begin(), values.end());

    ll res = 0;
    for (int i = (int)(values.size()) - 1; i >= (int)(values.size()) - m; i --)
        res += values[i];

        //exit(0);
    return res;*/
}

void divide(int l, int r, int optl, int optr)
{
    if (l > r)
        return;

    ///cout << l << " " << r << " " << optl << " " << optr << endl;
    int mid = max(optl + m - 1, (l + r) / 2), opt = -1;
    if (mid > r)
        return;

    for (int i = optl; i <= min(optr, mid); i ++)
    {
        ///cout << "check " << mid << " " << i << endl;
        if (mid - i + 1 >= m)
        {
            ll sum = - e[mid].s + e[i].s + cost(i, mid);
            ///cout << "alive " << " " << sum << endl;
            if (sum > dp[mid])
            {
                dp[mid ] = sum;
                opt = i;
            }
        }
    }


    //cout << "pos " << mid << " " << opt << endl;

    divide(l, mid - 1, optl, opt);
    divide(mid + 1, r, opt, optr);

}

void print()
{
    ll best = -inf;
    for (int i = 1; i <= n; i ++)
        best = max(best, dp[i]);
    cout << best << endl;
}
void precompute()
{
    sort(e + 1, e + n + 1, cmp_second);
    vector < pair < ll, ll > > val;
    for (int i = 1; i <= n; i ++)
    {
        e[i].idx = i;
        val.push_back({e[i].v, i});
    }

    sort(val.begin(), val.end());
    for (int i = 0; i < n; i ++)
    {
        rev[val[i].second] = i + 1;
        num[i + 1] = val[i].first;
    }

    for (int i = 1; i <= n; i ++)
        dp[i] = -inf;
}
void solve()
{
    input();
    precompute();
    divide(1, n, 1, n);
    print();
}

int main()
{
    speed();
    solve();
    return 0;
}

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