Submission #848339

#	Time	Username	Problem	Language	Result	Execution time	Memory
848339		yangjl	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	122 ms	17120 KiB

bulves

#include<iostream>
#include<cmath>
#include<cstring>
#include<cassert>
#include<string>
#include<queue>
#include<deque>
#include<stack>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<vector>
#include<set>
#include<unordered_set>
#include<bitset>
#include<climits>
#include<numeric>
#include<functional>
#include<iomanip>
#ifdef YJL
#include<debug.h>
#else
#define debug(args...)0
#define debug_n(a,n)0
#endif
#define ALL(a) a.begin(),a.end()
using namespace std;
using ll=long long;

constexpr ll inf = numeric_limits<ll>::max()/2;
struct slope_trick_concave {
    priority_queue<ll> ql;
    priority_queue<ll,vector<ll>,greater<>> qr;
    ll dl,dr;// 左右堆中斜率改变点的懒标记
    ll height;// 最低点高度
    slope_trick_concave(): dl(0), dr(0), height(0) {
        ql.push(-inf);
        qr.push(inf);
    }
    // g(x) = min{i = x-sub,x+add} (f(x))
    void range_min(ll sub, ll add) {
        dl-=add;
        dr+=sub;
    }
    // f(x) = g(x) + |x-c|
    void add(ll c) {
        ll xl=ql.top()+dl;
        ll xr=qr.top()+dr;
        if(xl <= c && c <= xr) {
            ql.push(c-dl);
            qr.push(c-dr);
        }else if(c < xl) {
            height+=xl-c;
            qr.push(xl-dr);
            ql.pop();
            ql.push(c-dl);
            ql.push(c-dl);
        }else {
            height+=c-xr;
            ql.push(xr-dl);
            qr.pop();
            qr.push(c-dr);
            qr.push(c-dr);
        }
    }
    void pref_min() {
        while(qr.size()>1)
            qr.pop();
    }
};

constexpr int N = 5e5 + 10;
int n;
ll c[N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin>>n;
    for(int i=1,x,y; i<=n; ++i) {
        cin>>x>>y;
        c[i]=c[i-1]+x-y;
    }
    // [0,c[n]]
    ll ans=0;
    slope_trick_concave sp;
    for(int i=1; i<=n; ++i) {
        if(c[i]<0) {
            ans+=-c[i];
            c[i]=0;
        }
        if(c[i]>c[n]) {
            ans+=c[i]-c[n];
            c[i]=c[n];
        }
        sp.add(c[i]);
        sp.pref_min();
    }
    cout << ans + sp.height;
    return 0;
}
/*


We want sum[] to be non-decreasing
An operation: choose i, then sum[i] += 1 or sum[i] -= 1
sum[0] must be >= 0
sum[N - 1] cannot be operated
This is classic Slope Trick

*/

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