제출 #772254

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
772254		danikoynov	Potatoes and fertilizers (LMIO19_bulves)	C++14	30 / 100	367 ms	39416 KiB

bulves

#include <iostream>
#include<stdio.h>
#include<cmath>
#include <set>
#include <cassert>
#include <numeric>
#include <fstream>

#define endl '\n'
#define int long long
typedef long long ll;

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) /// adds |x - 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);
        }
    }


    void print_slope_trick()
    {
        std::cout << "left_slope" << endl;
        for (int cor : left_set)
            std::cout << cor << " ";
        std::cout << endl;
        std::cout << "right_slope" << endl;
        for (int cor : right_set)
            std::cout << cor << " ";
        std::cout << endl;
        std::cout << "height " << height << endl;
    }


    void prefix_minimum()
    {


        right_set.clear();
        ///right_set.clear();
    }

    ll query_vlaue(ll debit)
    {

        ll last = get_left(), slope = 0, base = height;
        while(left_set.size() > 0 && get_left() > debit)
        {
            ll distance = last - get_left();
            base = base + distance * slope;
            slope ++;
            last = last - distance;
            assert(left_set.size() > 0);
            left_set.erase(prev(left_set.end()));
        }

        if (slope != 0)
        {
            assert(last >= debit);
            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;
    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];
    }


    ll sum = 0;
    for (int i = 1; i <= n; i ++)
    {
        sum += abs(pref[i]);
    }
    slope_trick st;

    ll cnt = 0;
    for (int i = 1; i <= n; i ++)
    {
        if (pref[i] < 0)
        {
            st.height += -pref[i];
            cnt ++;
            st.add_basic(0);
        }
        else
            st.add_basic(pref[i]), cnt ++;
        st.prefix_minimum();
        //std::cout << "--------------------" << endl;
        // st.print_slope_trick();
    }
    ///std::cout << "dasdas" << endl;

    ll sumf = 0;
    for (ll val : st.left_set)
        sumf += val;
    sumf += st.height;

    ll ans = st.query_vlaue(pref[n]);

    ///std::cout << "-----------------" << endl;
    std::cout << ans << endl;
}

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

signed main()
{

    ///speed();
    ///freopen("test.txt","r", stdin);

    solve();

    return 0;
}

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