제출 #1172239

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1172239		jill	Cake 3 (JOI19_cake3)	C++20	0 / 100	85 ms	219712 KiB

cake3

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
using ll = long long;
using pii = pair<ll, ll>;

const ll maxn = 4000005, inf = 1000000000, oo = 1000000000000000000LL;
ll n, m, dp[2][maxn];
pii a[maxn];

struct WT
{
    struct node
    {
        int l, r;
        vector<ll> x;
        vector<ll> s;
    } t[maxn];
    int build(vector<ll> &seq, ll A = 0, ll B = inf)
    {
        static int idxNode = 0;
        if (seq.empty())
            return -1;
        int cur = idxNode++;
        t[cur].x.assign(seq.size(), 0);
        t[cur].s.assign(seq.size(), 0);
        if (A == B)
            return cur;
        ll mid = (A + B) / 2;
        vector<ll> left_seq, right_seq;
        for (int i = 0; i < (int)seq.size(); i++)
        {
            if (seq[i] <= mid)
            {
                left_seq.push_back(seq[i]);
            }
            else
            {
                t[cur].x[i] = 1;
                t[cur].s[i] = seq[i];
                right_seq.push_back(seq[i]);
            }
        }
        for (int i = (int)seq.size() - 2; i >= 0; i--)
        {
            t[cur].x[i] += t[cur].x[i + 1];
            t[cur].s[i] += t[cur].s[i + 1];
        }
        t[cur].l = build(left_seq, A, mid);
        t[cur].r = build(right_seq, mid + 1, B);
        return cur;
    }

    int map_left(int nd, int i)
    {
        return i >= 0 ? i - t[nd].x[i] : -1;
    }
    int map_right(int nd, int i)
    {
        return i >= 0 ? t[nd].x[i] - 1 : -1;
    }

    int countRight(int cur, int l, int r)
    {
        if (l > r)
            return 0;
        ll totalR = t[cur].x[l];
        ll beyond = (r + 1 < (int)t[cur].x.size()) ? t[cur].x[r + 1] : 0;
        return (int)(totalR - beyond);
    }

    ll sumRight(int cur, int l, int r)
    {
        if (l > r)
            return 0LL;
        ll totalR = t[cur].s[l];
        ll beyond = (r + 1 < (int)t[cur].s.size()) ? t[cur].s[r + 1] : 0LL;
        return totalR - beyond;
    }

    ll queryUtil(int node, int A, int B, int l, int r, int k)
    {
        if (node == -1 || l > r || k <= 0)
            return 0LL;
        if (A == B)
        {
            int countSeg = (r - l + 1);
            int take = min(countSeg, k);
            return 1LL * take * A;
        }
        int mid = (A + B) >> 1;
        int totalR = countRight(node, l, r);
        if (totalR >= k)
        {
            int newL = map_right(node, l - 1) + 1;
            int newR = map_right(node, r);
            return queryUtil(t[node].r, mid + 1, B, newL, newR, k);
        }
        else
        {
            ll sumR = sumRight(node, l, r);
            int newL = map_left(node, l - 1) + 1;
            int newR = map_left(node, r);
            return sumR + queryUtil(t[node].l, A, mid, newL, newR, k - totalR);
        }
    }

    ll query(int l, int r, int k)
    {
        if (l > r)
            return 0LL;
        return queryUtil(0, 0, inf, l, r, k);
    }
} tree;

vector<ll> b;

void calc(int x, int l, int r, int opl, int opr)
{
    stack<tuple<int, int, int, int>> st;
    st.push({l, r, opl, opr});
    while (!st.empty())
    {
        auto [L, R, opL, opR] = st.top();
        st.pop();
        if (L > R)
            continue;
        int mid = (L + R) >> 1;
        pii best = {-oo, -1};
        int limit = min(mid - 1, opR);
        for (int k = opL; k <= limit; k++)
        {
            ll candidate = tree.query(k + 1, mid - 1, m - 2) + a[mid].fi + a[k].fi - 2 * abs(a[mid].se - a[k].se);
            best = max(best, {candidate, k});
        }
        dp[x][mid] = best.fi;
        int opt = best.se;
        st.push({L, mid - 1, opL, opt});
        st.push({mid + 1, R, opt, opR});
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i].fi >> a[i].se;
    }
    sort(a, a + n, [](const pii &x, const pii &y)
         { return x.se < y.se; });
    for (int i = 0; i < n; i++)
    {
        dp[0][i] = a[i].fi - a[i].se;
        b.push_back(a[i].fi);
    }
    tree.build(b);
    calc(1, 0, n - 1, 0, n - 1);
    cout << *max_element(dp[1], dp[1] + n);
    return 0;
}

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