Submission #772168

#	Time	Username	Problem	Language	Result	Execution time	Memory
772168		danikoynov	Potatoes and fertilizers (LMIO19_bulves)	C++14	20 / 100	1077 ms	19624 KiB

bulves

#include <iostream>
#include <set> 
#define endl '\n'

typedef long long ll;

struct slope_trick
{
    const int inf = 1e9;

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

    slope_trick()
    {
        height = 0;
    }

    void add_basic(int v) /// adds |x - v|
    {
        ll left = -inf;
        ll right = inf;
        if (!left_set.empty())
            left = *left_set.rbegin();
        if (!right_set.empty())
            right = *right_set.begin();


        if (v >= left && v <= right) /// function on base
        {
            left_set.insert(v);
            right_set.insert(v);
        }
        else
        if (v < left)
        {
            left_set.erase(left_set.find(left));
            right_set.insert(left);

            left_set.insert(v);
            left_set.insert(v);
            
            height = height + abs(left - v);
        }
        else
        if (v > right)
        {
            ///std::cout << v << " " << right << endl; 
            right_set.erase(right_set.find(right));
            left_set.insert(right);

            right_set.insert(v);
            right_set.insert(v);

            height = height + abs(right - v);
        }
    }


    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;
    }

    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 prefix_minimum()
    {
        while(left_set.size() > 0)
        {
            int val = *left_set.begin();
            if (val >= 0)
                break;
            left_set.erase(left_set.find(val));
        }

         ll slope = 0, base = height, last = get_right(), pos;
        while ((pos = get_right()) <= 0)
        {
            ll distance = pos - last;
            base = base + distance * slope;
            slope ++;
            last = last + distance;
            right_set.erase(right_set.find(pos));
        }
        
        if (slope != 0)
        {
            base = base + (- last) * slope;
            right_set.insert(0);
        }
        height = base;

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

    ll query_vlaue(ll debit)
    {   
        ll last = get_left(), slope = 0, base = height;
        while(last > debit)
        {
            ll distance = last - get_left();
            base = base + distance * slope;
            slope ++;
            last = last - distance;
            left_set.erase(left_set.find(*left_set.rbegin()));
        }
        if (slope != 0)
        {
            base = base + (last - debit) * slope;
        }

        return base;
    }
};


const int maxn = 500010;

int n;
ll a[maxn], b[maxn], 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];
    }

    
    slope_trick st;
    for (int i = 1; i <= n; i ++)
    {
        st.add_basic(pref[i]);
        st.prefix_minimum();
        //std::cout << "--------------------" << endl;
        //st.print_slope_trick();
    }
    ///std::cout << "dasdas" << endl;
    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);
}

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

Compilation message (stderr)

bulves.cpp: In member function 'void slope_trick::print_slope_trick()':
bulves.cpp:63:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   63 |         for (int cor : left_set)
      |         ^~~
bulves.cpp:65:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   65 |             std::cout << endl;
      |             ^~~

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