Submission #772236

#	Time	Username	Problem	Language	Result	Execution time	Memory
772236		danikoynov	Potatoes and fertilizers (LMIO19_bulves)	C++14	30 / 100	163 ms	45224 KiB

bulves

#include <iostream>
#include <set> 
#include <cassert>
#include <numeric>
#define endl '\n'
#define int long long
typedef long long ll;

const int BUFF_SIZE = 1e6;
int buffPos = BUFF_SIZE - 1;
char buff[BUFF_SIZE];

void readChar()
{
    if (++buffPos == BUFF_SIZE) fread(buff, BUFF_SIZE, 1, stdin), buffPos = 0;
}

void readInt(int &num)
{
    num = 0;
    for (; '0' > buff[buffPos] || buff[buffPos] > '9' ; readChar());
    for (; '0' <= buff[buffPos] && buff[buffPos] <= '9' ; readChar())
        num = 10 * num + buff[buffPos] - '0';
}

struct slope_trick
{
    const ll inf = 1e18;
 
    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;
int a[maxn], b[maxn];
ll x[maxn], pref[maxn];
 
void solve()
{
    readInt(n);
    for (int i = 1; i <= n; i ++)
    {
        readInt(a[i]);
        readInt(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:79:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   79 |         for (int cor : left_set)
      |         ^~~
bulves.cpp:81:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   81 |             std::cout << endl;
      |             ^~~
bulves.cpp: In function 'void readChar()':
bulves.cpp:15:38: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     if (++buffPos == BUFF_SIZE) fread(buff, BUFF_SIZE, 1, stdin), buffPos = 0;
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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