Submission #157179

#	Time	Username	Problem	Language	Result	Execution time	Memory
157179		combi1k1	Cake 3 (JOI19_cake3)	C++14	0 / 100	2 ms	376 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;
int V[N];
int tot;

namespace MySet {
    ii  t[N << 1];
    int L = 1;
    int R = 0;

    int upd(int p,int v)    {
        int x = v * V[p];
        int y = v;
        for(p += tot - 1 ; p ; p >>= 1)
            t[p].X += x,
            t[p].Y += y;
        return  1;
    }
    int get(int &c,int i)   {
        if (c == 0) return  0;
        if (c >= t[i].Y)    {
            c -= t[i].Y;
            return  t[i].X;
        }
        if (i >= tot)   {
            int x = t[i].X / t[i].Y * c;
            c = 0;  return  x;
        }

        int ans  = get(c,i << 1 | 1);
            ans += get(c,i << 1);
        return  ans;
    }
    void move(int l,int r)  {
        while (L > l)   upd(T[--L].Y, 1);
        while (R < r)   upd(T[++R].Y, 1);
        while (L < l)   upd(T[L++].Y,-1);
        while (R > r)   upd(T[R--].Y,-1);
    }
};

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,
        V[i] = T[i].Y;

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

    tot = unique(V + 1,V + 1 + n) - V;

    for(int i = 1 ; i <= n ; ++i)
        T[i].Y = lower_bound(V + 1,V + 1 + n,T[i].Y) - V;

    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 cnt = k;
            int nxt = MySet::get(cnt,1) + V[T[m].Y] + V[T[i].Y] - 2 * (T[m].X - T[i].X);

            if (cur < nxt)  {
                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;
}

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