Submission #772264

#	Time	Username	Problem	Language	Result	Execution time	Memory
772264		danikoynov	Potatoes and fertilizers (LMIO19_bulves)	C++14	100 / 100	264 ms	39568 KiB

bulves

#include <iostream>
#include <set> 
#include <cassert>
#include <numeric>
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
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) /// 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];
    }
 
    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();
        //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);
}
 
signed 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: 24 / 24
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 36 / 36