이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
}
// 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);
}
}
// g(x) = min{i = x-sub,x+add} (f(x))
void range_min(ll sub, ll add) {
dl-=add;
dr+=sub;
}
void pref_min() {
dr=0;
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
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |