Submission #1137377

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137377		trMatherz	Cake 3 (JOI19_cake3)	C++20	24 / 100	4094 ms	171052 KiB

cake3

#include <iostream> 
 
 
// #include <fstream>
// std::ifstream cin ("tttt.in");
// std::ofstream cout ("tttt.out");
 
 
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <random>
#include <chrono>
#include <bitset>
#include <complex>
 

using namespace std;
using namespace __gnu_pbds;
 
#define ll long long
#define f first
#define s second
template <class T> using iset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T, typename U>
bool emin(T &a, const U &b) { return b < a ? a = b, true : false; }
template <typename T, typename U>
bool emax(T &a, const U &b) { return b > a ? a = b, true : false; }
typedef uint64_t hash_t;
ll const inf = (ll) 1e15 + 7; 
int const M = (ll) 1e9 + 7; 
int const IM = (ll) 5e8 + 4; 


struct wave {
    int n; 
    vector<vector<ll>> a, pre; 
    vector<ll> v; 
    void init(vector<ll> b) {
        map<ll, int> c; n = 0; 
        for(auto &u : b) c[u] = 0; 
        v = vector<ll>(c.size());
        for(auto &u : c) v[u.s = n++] = u.f; 
        for(auto &u : b) u = c[u]; 
        a = pre = vector<vector<ll>>(n * 4, {0}); 
        build(b); 
    }
    void build(vector<ll> b, int x, int l, int r) {
        for(auto &u : b) pre[x].push_back(pre[x].back() + v[u]); 
        if(l == r) return; 
        int m = (l + r) / 2; 
        vector<ll> nex[2]; 
        for(auto &u : b) a[x].push_back(a[x].back() + (u <= m)); 
        for(auto &u : b) nex[u > m].push_back(u); 
        build(nex[0], x * 2, l, m); 
        build(nex[1], x * 2 + 1, m + 1, r); 
    }
    ll get(int rl, int rr, int c, int x, int l, int r) {
        if(l == r) return c * v[l]; 
        int m = (l + r) / 2, nl = a[x][rl - 1], nr = a[x][rr]; 
        if(nr - nl >= c) return get(nl + 1, nr, c, x * 2, l, m); 
        return pre[x * 2][nr] - pre[x * 2][nl] + get(rl - nl, rr - nr, c - nr + nl, x * 2 + 1, m + 1, r); 
    }
    ll get(int rl, int rr, int c) { return get(rl + 1, rr + 1, c, 1, 0, n); }
    void build(vector<ll> b) { build(b, 1, 0, n); }
} w; 
int n, k; 
vector<pair<ll, ll>> a; 
ll an = -inf; 
void go(int rl = 0, int rr = n - 1, int l = 0, int r = n - 1) {
    int m = (l + r) / 2; 
    pair<ll, int> bes = {-inf, -1}; 
    for(int i = max(rl, m + k - 1); i <= rr; i++) 
        emax(bes, make_pair(-w.get(m, i, k) - 2 * (a[i].s - a[m].s), i)); 
    emax(an, bes.f); 
    if(l == r) return; 
    go(rl, (bes.s != -1 ? bes.s : rr), l, m); go((bes.f != -1 ? : bes.f), rr, m + 1, r); 
}
int main() {
    cin >> n >> k; 
    a = vector<pair<ll, ll>>(n); for(auto &u : a) cin >> u.f >> u.s; 
    sort(a.begin(), a.end(), [](auto x, auto y){ return x.s < y.s; }); 
    vector<ll> b(n); for(int i = 0; i < n; i++) b[i] = -a[i].f; 
    w.init(b); 
    go(); 
    cout << an; 
}

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