Submission #851294

#	Time	Username	Problem	Language	Result	Execution time	Memory
851294		yangjl	Potatoes and fertilizers (LMIO19_bulves)	C++17	100 / 100	125 ms	20284 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 tagl,tagr;// 左右堆中斜率改变点的懒标记
    ll height;// 最低点高度
    slope_trick_concave(): tagl(0), tagr(0), height(0) {
        ql.push(-inf);
        qr.push(inf);
    }
    ll get_left() {
        return ql.top()+tagl;
    }
    ll get_right() {
        return qr.top()+tagr;
    }
    // f(x) = g(x) + |x-c|
    void add(ll c) {
        ll xl=get_left();
        ll xr=get_right();
        if(xl <= c && c <= xr) {
            ql.push(c-tagl);
            qr.push(c-tagr);
        }else if(c < xl) {
            height+=xl-c;
            qr.push(xl-tagr);
            ql.pop();
            ql.push(c-tagl);
            ql.push(c-tagl);
        }else {
            height+=c-xr;
            ql.push(xr-tagl);
            qr.pop();
            qr.push(c-tagr);
            qr.push(c-tagr);
        }
    }
    // g(x) = min_{y=x+low, x+high} f(y)
    void range_min(ll low, ll high) {
        tagl-=high;
        tagr-=low;
    }
    // g(x) = min_{y=-inf, x} f(y)
    void pref_min() {
        tagr=0;
        while(qr.size()>1)
            qr.pop();
    }
};

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin>>n;
    vector<ll> a(n),b(n);
    for(int i=0; i<n; ++i) {
        cin>>a[i];
         cin>>b[i];
        a[i]-=b[i];
        if(i) a[i]+=a[i-1];
    }
    // for(int i=0; i<n; ++i) {
       
    // }

    slope_trick_concave sp;
    ll ans=0;
    for(int i=0; i<n; ++i) {
        if(a[i]<0) {
            ans-=a[i];
            a[i]=0;
        }
        if(a[i]>a[n-1]) {
            ans+=a[i]-a[n-1];
            a[i]=a[n-1];
        }
        sp.add(a[i]);
        sp.pref_min();
    }
    cout<<ans+sp.height;
    return 0;
}
/*
a[i]++, a[i+1]--
前缀和
a[i]++

最后
0<=a[0]<=..<=a[n-1]
*/

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