Submission #921980

#	Time	Username	Problem	Language	Result	Execution time	Memory
921980		boris_mihov	Cake 3 (JOI19_cake3)	C++17	100 / 100	1271 ms	18672 KiB

cake3

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXN = 200000 + 10;
const llong INF = 1e18;

int n, k;
int v[MAXN];
int c[MAXN];
int sortedV[MAXN];
struct SegmentTree
{
    struct Node
    {
        llong sum;
        int cnt;

        Node()
        {
            sum = cnt = 0;
        }

        friend Node operator + (const Node &left, const Node &right)
        {
            Node res;
            res.sum = left.sum + right.sum;
            res.cnt = left.cnt + right.cnt;
            return res;
        }
    };

    Node tree[4*MAXN];
    void update(int l, int r, int node, int queryPos)
    {
        if (l == r)
        {
            if (tree[node].cnt == 1)
            {
                tree[node].sum = 0;
                tree[node].cnt = 0;
            } else
            {
                tree[node].sum = sortedV[l];
                tree[node].cnt = 1;
            }

            return;
        }

        int mid = (l + r) / 2;
        if (queryPos <= mid) update(l, mid, 2*node, queryPos);
        else update(mid + 1, r, 2*node + 1, queryPos);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    int findPos(int l, int r, int node, int k)
    {
        if (l == r)
        {
            return l;
        }

        int mid = (l + r) / 2;
        if (tree[2*node].cnt >= k)
        {
            return findPos(l, mid, 2*node, k);
        } else
        {
            return findPos(mid + 1, r, 2*node + 1, k - tree[2*node].cnt);
        }
    }

    llong query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node].sum;
        }

        llong res = 0;
        int mid = (l + r) / 2;
        if (queryL <= mid) res += query(l, mid, 2*node, queryL, queryR);
        if (mid + 1 <= queryR) res += query(mid + 1, r, 2*node + 1, queryL, queryR);
        return res;
    }

    void update(int pos)
    {
        update(1, n, 1, pos);
    }

    llong query()
    {
        int to = findPos(1, n, 1, k);
        return query(1, n, 1, 1, to);
    }
};

int inOrder[MAXN];
int revOrder[MAXN];
std::pair <int,int> toSort[MAXN];
SegmentTree tree;

int ptrL = 1;
int ptrR = 0;
llong cost(int l, int r)
{
    r--;
    l++;
    while (ptrL < l)
    {
        tree.update(revOrder[ptrL]);
        ptrL++;
    }

    while (ptrL > l)
    {
        ptrL--;
        tree.update(revOrder[ptrL]);
    }

    while (ptrR > r)
    {
        tree.update(revOrder[ptrR]);
        ptrR--;
    }

    while (ptrR < r)
    {
        ptrR++;
        tree.update(revOrder[ptrR]);
    }

    return tree.query() + v[l - 1] + v[r + 1] - 2 * (c[r + 1] - c[l - 1]);
}

llong ans = -INF;
void divide(int l, int r, int optL, int optR)
{
    int opt = -1;
    llong curr = -INF;
    int mid = (l + r) / 2;

    for (int i = std::max(mid + k + 1, optL) ; i <= optR ; ++i)
    {
        llong res = cost(mid, i);
        if (res > curr)
        {
            curr = res;
            opt = i;
        }
    }

    ans = std::max(ans, curr);
    if (l < mid) divide(l, mid - 1, optL, opt);
    if (mid < r) divide(mid + 1, r, opt, optR);
}

void solve()
{
    std::sort(toSort + 1, toSort + 1 + n);
    for (int i = 1 ; i <= n ; ++i)
    {
        c[i] = toSort[i].first;
        v[i] = toSort[i].second;
    }

    std::iota(inOrder + 1, inOrder + 1 + n, 1);
    std::sort(inOrder + 1, inOrder + 1 + n, [&](int x, int y)
    {
        return v[x] > v[y];
    }); 

    for (int i = 1 ; i <= n ; ++i)
    {
        sortedV[i] = v[inOrder[i]];
        revOrder[inOrder[i]] = i;
    }

    k -= 2;
    divide(1, n - k - 1, 1, n);
    std::cout << ans << '\n';
}

void input()
{
    std::cin >> n >> k;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> toSort[i].second >> toSort[i].first;
    }
}   

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}

int main()
{
    fastIOI();
    input();
    solve();

    return 0;
}

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