제출 #144236

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
144236		osaaateiasavtnl	Cake 3 (JOI19_cake3)	C++14	100 / 100	1460 ms	206304 KiB

cake3

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
const int N = 2e5 + 7, INF = 1e18 + 7;
int n, m;
struct El { int v, c; } a[N];
struct Node { int cnt, sum; Node *l, *r; Node () { cnt = sum = 0; l = r = NULL; } };
vector <int> c;
Node *build(int tl, int tr) {
    Node *ans = new Node();
    if (tl == tr) return ans;
    int tm = (tl + tr) >> 1;
    ans->l = build(tl, tm); ans->r = build(tm + 1, tr);
    return ans;
}
void relax(Node *t) { t->cnt = t->l->cnt + t->r->cnt; t->sum = t->l->sum + t->r->sum; }
Node *add(Node *t, int tl, int tr, int p) {
    Node *ans = new Node();
    if (tl == tr) { ans->cnt = t->cnt + 1; ans->sum = t->sum + c[p]; return ans; }
    int tm = (tl + tr) >> 1;
    if (p <= tm) { ans->l = add(t->l, tl, tm, p); ans->r = t->r; }
    else { ans->l = t->l; ans->r = add(t->r, tm + 1, tr, p); }
    relax(ans); return ans;
}
int get(Node *l, Node *r, int tl, int tr, int k) {
    if (tl == tr) return c[tl] * k;
    int tm = (tl + tr) >> 1;
    int t = r->r->cnt - l->r->cnt;
    if (k <= t) return get(l->r, r->r, tm + 1, tr, k);
    else return get(l->l, r->l, tl, tm, k - t) + (r->r->sum - l->r->sum);
}
Node *t[N];
int get(int l, int r) {
    return get(t[l - 1], t[r], 0, N, m) - 2 * (a[r].c - a[l].c); 
}
int ans = -INF;
int get(int i, int l, int r) {
    int best = -INF, pos = l;
    for (int j = l; j <= r && m <= i - j + 1; ++j) {
        int nn = get(j, i);
        if (best < nn) { best = nn; pos = j; }
    }
    ans = max(ans, best);
    return pos;
}
void solve(int l, int r, int ll, int rr) {
    if (r < l) return;
    int m = (l + r) >> 1; int mm = get(m, ll, rr);
    if (l == r) return;
    solve(l, m - 1, ll, mm); solve(m + 1, r, mm, rr);
}
bool comp(El a, El b) { return a.c < b.c; }
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) { cin >> a[i].v >> a[i].c; c.app(a[i].v); }
    sort(c.begin(), c.end()); c.resize(unique(all(c)) - c.begin());
    sort(a + 1, a + n + 1, comp);
    t[0] = build(0, N);
    for (int i = 1; i <= n; ++i) {
        t[i] = add(t[i - 1], 0, N, lower_bound(c.begin(), c.end(), a[i].v) - c.begin());
    }
    solve(1, n, 1, n); cout << ans << '\n';
}   

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