Submission #697158

#	Time	Username	Problem	Language	Result	Execution time	Memory
697158		elkernos	Cake 3 (JOI19_cake3)	C++17	100 / 100	3508 ms	16588 KiB

cake3

// while (clock()<=69*CLOCKS_PER_SEC)
// #pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("O3")
// #pragma GCC target ("avx2")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

#define sim template <class c
#define ris return *this
#define dor > debug &operator<<
#define eni(x)                                                                    \
    sim > typename enable_if<sizeof dud<c>(0) x 1, debug &>::type operator<<(c i) \
    {
sim > struct rge {
    c b, e;
};
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c *x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef XOX
    ~debug()
    {
        cerr << endl;
    }
    eni(!=) cerr << boolalpha << i;
    ris;
} eni(==) ris << range(begin(i), end(i));
}
sim, class b dor(pair<b, c> d)
{
    ris << "" << d.first << " --> " << d.second << "";
}
sim dor(rge<c> d)
{
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
        *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
}
#else
    sim dor(const c &)
    {
        ris;
    }
#endif
}
;
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#ifdef XOX
#warning Times may differ!!!
#endif

#define endl '\n'
#define pb emplace_back
#define vt vector
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define int long long

const int oo = 1e18 + 213;

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i].first >> a[i].second;
    }
    sort(1 + all(a), [&](auto &i, auto &j) {
        return i.second < j.second;
    });
    int ret = -oo;
    multiset<int> small, big;
    int sum = 0, L = 1, R = n;
    auto balance = [&]() {
        if (!size(small) || !size(big)) return;
        if (size(big) < m) {
            int dod = *small.rbegin();
            small.erase(small.find(dod));
            sum += dod;
            big.insert(dod);
            return;
        }
        if (*small.rbegin() > *big.begin()) {
            int usu_1 = *small.rbegin();
            int usu_2 = *big.begin();
            big.erase(big.find(usu_2));
            small.erase(small.find(usu_1));
            big.insert(usu_1);
            small.insert(usu_2);
            sum += usu_1 - usu_2;
        }
    };
    auto dod = [&](int x) {
        if (size(big) < m) {
            big.insert(x);
            sum += x;
        }
        else small.insert(x);
        balance();
    };
    auto usu = [&](int x) {
        if (small.find(x) != small.end()) small.erase(small.find(x));
        else {
            big.erase(big.find(x));
            sum -= x;
        }
        balance();
    };
    auto napraw = [&](int new_l, int new_r) {
        while (new_l < L)
            dod(a[--L].first);
        while (R < new_r)
            dod(a[++R].first);
        while (L < new_l)
            usu(a[L++].first);
        while (new_r < R)
            usu(a[R--].first);
    };
    for (int i = 1; i <= n; i++)
        dod(a[i].first);
    function<void(int, int, int, int)> rek = [&](int l, int r, int lo, int hi) {
        debug() << imie(l) imie(r) imie(lo) imie(hi);
        if (l > r || lo > hi) return;
        int ans = LLONG_MIN, pos = hi;
        int mid = (l + r) / 2;
        for (int i = max(lo, mid + m - 1); i <= hi; i++) {
            napraw(mid, i);
            int maybe = sum - 2 * (a[i].second - a[mid].second);
            debug() << imie(mid) imie(i) imie(maybe);
            if (maybe > ans) {
                ans = maybe;
                pos = i;
            }
        }
        ret = max(ret, ans);
        rek(l, mid - 1, lo, pos);
        rek(mid + 1, r, pos, hi);
    };
    rek(1, n, m, n);
    cout << ret << endl;
}

Compilation message (stderr)

cake3.cpp: In lambda function:
cake3.cpp:90:23: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   90 |         if (size(big) < m) {
      |             ~~~~~~~~~~^~~
cake3.cpp: In lambda function:
cake3.cpp:108:23: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  108 |         if (size(big) < m) {
      |             ~~~~~~~~~~^~~

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