Submission #157175

#	Time	Username	Problem	Language	Result	Execution time	Memory
157175		combi1k1	Cake 3 (JOI19_cake3)	C++14	24 / 100	4089 ms	18684 KiB

cake3

#include<bits/stdc++.h>

using namespace std;

#define X   first
#define Y   second
#define int long long

const int   N   = 2e5 + 1;
const int   inf = 1e18;

typedef pair<int,int>   ii;

ii  T[N];
int n, k;

namespace MySet {
    int L = 1;
    int R = 0;
    int Sum = 0;

    multiset<int>   S1;
    multiset<int>   S2;

    set<int>::iterator it = S1.begin();

    void add(int x) {
        S1.insert(x);
        S2.insert(x);
        Sum += x;

        if (S2.size() > k)  {
            if(*it <= x)    ++it;
            Sum -= *(S2.begin());
            S2.erase(S2.begin());
        }
        else    it = S1.begin();
    }
    void rem(int x) {
        if(*it == x)
            it++;
        if (S1.find(x) != S1.end()) S1.erase(S1.find(x));
        if (S2.find(x) != S2.end()) S2.erase(S2.find(x));

        if (S2.size() < k)  {
            Sum -= x;   x = *(--it);
            Sum += x;   S2.insert(x);
        }
    }
    void move(int l,int r)  {
        while (L > l)   add(T[--L].Y);
        while (R < r)   add(T[++R].Y);
        while (L < l)   rem(T[L++].Y);
        while (R > r)   rem(T[R--].Y);
    }
};

using MySet::Sum;

signed main()   {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> k;

    for(int i = 1 ; i <= n ; ++i)
        cin >> T[i].Y >> T[i].X;

    sort(T + 1,T + 1 + n);

    queue<ii>   q;

    q.push({k * N + n,N + n - k + 1});  k -= 2;

    int ans = -1e18;

    while(q.size()) {
        int l = q.front().X / N;
        int r = q.front().X % N;
        int A = q.front().Y / N;
        int B = q.front().Y % N;
        q.pop();

        int m = (l + r) / 2;
        int opt = 0;
        int cur = -1e18;

        for(int i = A ; i <= min(B,m - k - 1) ; ++i)    {
            MySet::move(i + 1,m - 1);

            int nxt = Sum + T[m].Y + T[i].Y - 2 * (T[m].X - T[i].X);
            if (nxt > cur)  {
                cur = nxt;
                opt = i;
            }
        }

        ans = max(ans,cur);

        if (l < m)  q.push({l * N + m - 1,A * N + opt});
        if (m < r)  q.push({m * N + r + N,opt * N + B});
    }

    cout << ans << endl;
}

Compilation message (stderr)

cake3.cpp: In function 'void MySet::add(long long int)':
cake3.cpp:32:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (S2.size() > k)  {
             ~~~~~~~~~~^~~
cake3.cpp: In function 'void MySet::rem(long long int)':
cake3.cpp:45:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (S2.size() < k)  {
             ~~~~~~~~~~^~~

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