Submission #1203013

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203013		Nelt	Potatoes and fertilizers (LMIO19_bulves)	C++17	30 / 100	1095 ms	984 KiB

bulves

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl "\n"
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T, typename key = less<T>>
using ordered_set = tree<T, null_type, key, rb_tree_tag, tree_order_statistics_node_update>;
struct Set
{
    multiset<ll> l, r;
    ll suml = 0, sumr = 0;
    void relax()
    {
        while (!l.empty() and !r.empty() and *l.rbegin() > *r.begin())
        {
            suml -= *l.rbegin();
            sumr += *l.rbegin();
            r.insert(*l.rbegin());
            l.erase(--l.end());
        }
        while (l.size() > r.size())
        {
            suml -= *l.rbegin();
            sumr += *l.rbegin();
            r.insert(*l.rbegin());
            l.erase(--l.end());
        }
        while (r.size() > l.size())
        {
            suml += *r.begin();
            sumr -= *r.begin();
            l.insert(*r.begin());
            r.erase(r.begin());
        }
    }
    ll median()
    {
        return l.empty() ? 0 : *l.rbegin();
    }
    ll cost()
    {
        return median() * l.size() - suml + sumr - median() * r.size();
    }
    void add(ll x)
    {
        l.insert(x);
        suml += x;
        relax();
    }
    ll pop()
    {
        if (r.empty())
        {
            ll x = *l.rbegin();
            suml -= x;
            l.erase(--l.end());
            relax();
            return x;
        }
        ll x = *r.rbegin();
        sumr -= x;
        r.erase(--r.end());
        relax();
        return x;
    }
    bool empty()
    {
        return l.empty() and r.empty();
    }
    ll size()
    {
        return l.size() + r.size();
    }
};
void solve()
{
    ll n;
    cin >> n;
    ll a[n];
    {
        ll sum = 0;
        for (ll i = 0; i < n; i++)
        {
            ll x, y;
            cin >> x >> y;
            sum += x - y;
            a[i] = sum;
        }
    }
    ll ans = 0; 
    vector<Set> v;
    for (ll i = 0; i < n; i++)
    {
        if (a[i] < 0) ans -= a[i], a[i] = 0;
        if (a[i] > a[n - 1]) ans += a[i] - a[n - 1], a[i] = a[n - 1];
        v.push_back(Set());
        v.back().add(a[i]);
        while (v.size() >= 2 and v.back().median() <= v[v.size() - 2].median())
        {
            if (v.back().size() < v[v.size() - 2].size()) swap(v.back(), v.end()[-2]);
            while (!v.back().empty())
                v[v.size() - 2].add(v.back().pop());
            v.pop_back();
        }
    }
    for (auto i : v) ans += i.cost();
    cout << ans << endl;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // precomp();
    // cin >> t;
    for (ll cs = 1; cs <= t; cs++)
        solve();
    // cerr << "\nTime elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms\n";
}

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