Submission #772139

#	Time	Username	Problem	Language	Result	Execution time	Memory
772139		danikoynov	Potatoes and fertilizers (LMIO19_bulves)	C++14	0 / 100	3 ms	724 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 offset, height;

    slope_trick()
    {
        offset = 0;
        height = 0;
    }

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


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

            left_set.insert(v - offset);
            left_set.insert(v - offset);
            
            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 - offset);
            right_set.insert(v - offset);

            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;
    }
    void prefix_minimum()
    {
        while(right_set.size() > 0)
        {
            int val = *right_set.rbegin();
            if (val <= 0)
                break;
            right_set.erase(right_set.find(val));
        }
        ///right_set.clear();
    }

    ll query_vlaue()
    {
        return height;
    }
};


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();
    ///std::cout << "-----------------" << endl;
    std::cout << ans << endl;
}

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

Compilation message (stderr)

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

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