Submission #946383

#	Time	Username	Problem	Language	Result	Execution time	Memory
946383		LOLOLO	Cake 3 (JOI19_cake3)	C++17	100 / 100	1184 ms	26772 KiB

cake3

#include <bits/stdc++.h>
typedef long long ll;

#define           f    first
#define           s    second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)

using namespace std;
const int N = 2e5 + 100;
pair <ll, ll> seg[N * 4];
vector <ll> val;
vector <pair <ll, ll>> save;
map <int, int> mp;

void add(int id, int l, int r, int p, int val) {
    if (l > p || r < p)
        return;

    if (val < 0) {
        seg[id].s--;
    } else {
        seg[id].s++;
    }

    seg[id].f += val;
    if (l == r)
        return;

    int m = (l + r) / 2;
    add(id * 2, l, m, p, val);
    add(id * 2 + 1, m + 1, r, p, val); 
}

ll walk(int id, int l, int r, int re) {
    if (l == r) {
        return seg[id].f - val[l] * (seg[id].s - re);
    }

    int m = (l + r) / 2;
    if (seg[id * 2].s >= re)
        return walk(id * 2, l, m, re);

    ll t = walk(id * 2 + 1, m + 1, r, re - seg[id * 2].s);
    return seg[id * 2].f + t;
}

int n;
ll get(int m) {
    return walk(1, 0, n - 1, m);
}

ll ans = -1e16;
int l = 0, r = 0, sz;

void move(int L, int R) {
    while (r < R) {
        r++;
        add(1, 0, n - 1, save[r].s, val[save[r].s]);
    }

    while (l > L) {
        l--;
        add(1, 0, n - 1, save[l].s, val[save[l].s]);
    }

    while (l < L) {
        add(1, 0, n - 1, save[l].s, -val[save[l].s]);
        l++;
    }

    while (r > R) {
        add(1, 0, n - 1, save[r].s, -val[save[r].s]);
        r--;
    }
}

void dnc(int l, int r, int opl, int opr) {
    if (l > r || opl > opr)
        return;

    ll mx = -1e16;
    int m = (l + r) / 2, opt = opr;
    for (int j = max(m + sz - 1, opl); j <= opr; j++) {
        move(m, j);
        ll t = get(sz);
        if (mx < t - (save[j].f - save[m].f) * 2) {
            mx = t - (save[j].f - save[m].f) * 2;
            opt = j;
        }
    }

    dnc(l, m - 1, opl, opt);
    dnc(m + 1, r, opt, opr);
    ans = max(ans, mx);
}

ll solve() {
    cin >> n >> sz;
    
    for (int i = 0; i < n; i++) {
        int v, c;
        cin >> v >> c;
        save.pb({c, v});
        val.pb(v);
    }

    sort(all(save));
    uniquev(val);
    reverse(all(val));

    for (int i = 0; i < sz(val); i++)
        mp[val[i]] = i;

    for (auto &x : save) {
        x.s = mp[x.s];
    }

    l = r = 0;
    add(1, 0, n - 1, save[0].s, val[save[0].s]);    
    dnc(0, n - 1, 0, n - 1);
    return ans;
}

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

    int t = 1;
    //cin >> t;

    while (t--) {
        //solve();
        cout << solve() << '\n';
    }
    
    return 0;
}

/*
4 3
2 3
2 6 2
2 4 2
6 5 1
1 2 3
*/

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