Submission #772261

#	Time	Username	Problem	Language	Result	Execution time	Memory
772261		radoslav11	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	277 ms	40180 KiB

bulves

#include <bits/stdc++.h>
#define endl '\n'

typedef long long ll;

using namespace std;

struct slope_trick {
    const ll inf = 9223372036854775807ll;

    std::multiset < ll > left_set, right_set;
    ll height;

    slope_trick() {
        height = 0;
    }

    ll get_right() {
        if (right_set.empty()) return inf;
        return *right_set.begin();
    }

    ll get_left() {
        if (left_set.empty()) return -inf;
        return *left_set.rbegin();
    }

    void add_basic(ll v) {
        ll left = get_left(), right = get_right();

        if (v >= left && v <= right) {
            left_set.insert(v);
            right_set.insert(v);
        }
        else {
            if (v < left) {
                left_set.insert(v);
                left_set.insert(v);

                right_set.insert(left);
                left_set.erase(left_set.find(left));

                height = height + abs(v - left);
            }
            else {
                assert(false);
            }
        }
    }

    void prefix_minimum() {
        right_set.clear();
    }

    ll query_vlaue(ll debit) {
        ll last = get_left(), slope = 0, base = height;
        while(left_set.size() > 0 && get_left() > debit) {
            base = base + (last - get_left()) * slope;
            slope++;

            last = get_left();
            left_set.erase(left_set.find(last));
        }

        if (slope != 0) {
            base = base + (last - debit) * slope;
        }

        return base;
    }
};

const int maxn = 500010;

int n;
ll a[maxn], b[maxn];
ll x[maxn], pref[maxn];

void solve() {
    std::cin >> n;
    pref[0] = 0;
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i] >> b[i];
        x[i] = a[i] - b[i];
        pref[i] = pref[i - 1] + x[i];
    }

    slope_trick st;
    for (int i = 1; i <= n; i++) {
        if (pref[i] < 0) {
            st.height += -pref[i];
            st.add_basic(0);
        }
        else {
            st.add_basic(pref[i]);
        }
        st.prefix_minimum();
    }

    ll ans = st.query_vlaue(pref[n]);
    std::cout << ans << endl;
}

void speed()
{
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    std::cout.tie(NULL);
}

signed main()
{
    speed();
    solve();
    return 0;
}

• Subtask 1: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 36 / 36