제출 #1276806

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1276806		duckindog	Cake 3 (JOI19_cake3)	C++20	100 / 100	1564 ms	10648 KiB

cake3

#include <bits/stdc++.h>

using namespace std;

const int N = 200'000 + 10;
int n, m;
pair<int, int> p[N];

vector<int> rrh;
namespace IT { 
    int f[N << 2];
    long long g[N << 2];
 
    void update(int s, int l, int r, int p, int x) { 
        if (p < l || p > r) return;
        if (l == r) { 
            f[s] += x;
            g[s] += 1ll * rrh[l - 1] * x;
            return;
        }
        int mid = (l + r) >> 1;
        if (p <= mid) update(s << 1, l, mid, p, x);
        else update(s << 1 | 1, mid + 1, r, p, x);
        f[s] = f[s << 1] + f[s << 1 | 1];
        g[s] = g[s << 1] + g[s << 1 | 1];
    }
    long long query(int s, int l, int r, int k) {
        if (k <= 0 || !f[s]) return 0;
        if (k >= f[s]) return g[s];
        if (l == r) return 1ll * rrh[l - 1] * min(f[s], k);
        int mid = (l + r) >> 1;
        return query(s << 1, l, mid, k - f[s << 1 | 1]) + query(s << 1 | 1, mid + 1, r, k);
    }
}
int itL = 1, itR = 0;
void MO(int l, int r) { 
    while (itR < r) IT::update(1, 1, rrh.size(), p[++itR].first, 1);
    while (itL < l) IT::update(1, 1, rrh.size(), p[itL++].first, -1);
    while (itR > r) IT::update(1, 1, rrh.size(), p[itR--].first, -1);
    while (itL > l) IT::update(1, 1, rrh.size(), p[--itL].first, 1);
}

const long long MAX = 1'000'000'000'000'000;
long long f[N];
void dnc(int l, int r, int lt, int rt) { 
    int mid = (l + r) >> 1;
    
    auto& ret = f[mid];
    ret = -MAX;
    int opt = lt;

    for (int i = min(mid - 1, rt); i >= lt; --i) { 
        MO(i + 1, mid - 1);
        
        if (IT::f[1] >= m - 2) { 
            long long value = IT::query(1, 1, rrh.size(), m - 2);
            value += rrh[p[i].first - 1] + rrh[p[mid].first - 1];
            value += 2ll * (p[i].second - p[mid].second);
            
            if (ret < value) { 
                ret = value;
                opt = i;
            }
        }
    }
    
    if (l < mid) dnc(l, mid - 1, lt, opt);
    if (mid < r) dnc(mid + 1, r, opt, rt);
}

int32_t main() { 
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> p[i].first >> p[i].second;

    sort(p + 1, p + n + 1, [](const auto& a, const auto& b) { 
        return make_pair(a.second, a.first) < make_pair(b.second, b.first);
    });
    { // discrete
        for (int i = 1; i <= n; ++i) rrh.push_back(p[i].first);
        sort(rrh.begin(), rrh.end());
        rrh.erase(unique(rrh.begin(), rrh.end()), rrh.end());

        for (int i = 1; i <= n; ++i) { 
            p[i].first = upper_bound(rrh.begin(), rrh.end(), p[i].first) - rrh.begin();
        }
    }

    dnc(1, n, 1, n);
    cout << *max_element(f + 1, f + n + 1) << "\n";
}

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