Submission #718682

#	Time	Username	Problem	Language	Result	Execution time	Memory
718682		walterw	Cake 3 (JOI19_cake3)	C++17	100 / 100	2970 ms	216836 KiB

cake3

#include "bits/stdc++.h"

using namespace std;

void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    while (l != r) cout << *l << " \n"[++l == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.first >> a.second;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.first << ", " << a.second << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}

#ifdef local
#define test(args...) abc("[" + string(#args) + "]", args)
#else
#define test(args...) void(0)
#endif

using ll = long long;

#define int ll

pair<int, int> p[200005];

int v[200005], c[200005];

struct pqremove {
    priority_queue<ll, vector<ll>, greater<ll>> pq, rpq;

    ll sz;
    ll sum = 0;

    vector<pair<ll, ll>> ops;

    void init (int size) {
        sz = size;

        for (int i = 0; i < sz; i++) pq.push(-1e13);

        sum = sz * (ll) (-1e13);
    }

    void insert(int k) {
        while (!rpq.empty() && rpq.top() == pq.top()) {
            pq.pop();
            rpq.pop();
        }

        pq.push(k);
        sum += k;
        ops.emplace_back(0, k);
        sum -= pq.top();
        ops.push_back({1, pq.top()});
        pq.pop();
    }

    void undo(int t) {
        while (ops.size() > t) {
            auto [i, k] = ops.back();
            ops.pop_back();

            if (i == 0) {
                rpq.push(k);
                sum -= k;
            } else {
                pq.push(k);
                sum += k;
            }
        }

        while (!rpq.empty() && rpq.top() == pq.top()) {
            pq.pop();
            rpq.pop();
        }
    }
};

pqremove st;
ll dp[200005];
ll ans = -1e18;

void dnc(int l, int r, int lb, int rb) {
    if (l > r) return;

    int mid = (l + r) / 2;

    int t = st.ops.size();

    for (int i = mid - 1; i >= l && i > rb; i--) {
        st.insert(v[i]);
    }

    for (int i = min(mid - 1, rb); i >= lb; i--) {
        dp[i] = v[i] + v[mid] + st.sum - 2 * (c[mid] - c[i]);
        st.insert(v[i]);
    }

    st.undo(t);

    int maxsofar = lb;
    for (int i = min(mid - 1, rb); i >= lb; i--) {
        if (dp[i] >= dp[maxsofar]) {
            maxsofar = i;
        }
    }

    ans = max(ans, dp[maxsofar]);

    if (l <= mid - 1) {
        for (int i = min(l - 1, rb); i > maxsofar; i--) {
            st.insert(v[i]);
        }

        dnc(l, mid - 1, lb, maxsofar);

        st.undo(t);
    }

    if (r >= mid + 1) {
        for (int i = max(rb + 1, l); i <= mid; i++) {
            st.insert(v[i]);
        }

        dnc(mid + 1, r, maxsofar, rb);

        st.undo(t);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen("", "r", stdin);
//    freopen("", "w", stdout);
    int n, m; cin >> n >> m;

    st.init(m - 2);

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

    sort( p+ 1, p + 1 + n);

    for (int i = 1; i <= n; i++) {
        c[i] = p[i].first;
        v[i] = p[i].second;
    }

    dnc(1, n, 1, n);

    cout << ans;
}

Compilation message (stderr)

cake3.cpp: In member function 'void pqremove::undo(ll)':
cake3.cpp:69:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   69 |         while (ops.size() > t) {
      |                ~~~~~~~~~~~^~~

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