This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//[Author] tuxedcat
//[Date] 2023.05.07 14:40:59 KST
//[File] src/c.cpp
//[Library] https://github.com/tuxedcat/ps.cpp
//[Revision] e876fc2f8914923aefbd4b1a0920d88253b54882
/* ORIGINAL_MAIN_SOURCE
#include "core/base.h"
signed main(){
void solve();
// for(int ti=1,t=get<0>(input());ti<=t;ti++)
// print("Case #",ti,": "),
solve();
assert(cin.get()=='\n');
assert(cin.get()==EOF);
}
#include "dp/slope.h"
void solve(){
int n; cin>>n;
Arr<int> a(n);
for(int i=0;i<n;i++){
int x,y; cin>>x>>y;
a[i]=x-y;
}
Arr<int> b(n+1);
partial_sum(a.begin(),a.end(),b.begin());
// dbg(b);
LeftHull z;
for(int i=0;i<n;i++){
z.pf_dec( max(0ll,b[i]) );
z.sf_inc( min(b[n-1],b[i]) );
// dbg(z.argmin(),z.minval());
}
// dbg(z.argmin(),z.minval());
println(z.minval());
// auto dp=ARR(n,b[n-1]+1,-1ll);
// func(int,f,int x,int y){
// if(x==-1)
// return 0;
// auto&r=dp[x][y];
// if(~r)return r;
// r=inf<int>();
// for(int i=0;i<=y;i++)
// r=min(r,f(x-1,i))+abs(b[x]-y);
// return r;
// };
// println(f(n-1,b[n-1]));
}
*/
#include <bits/stdc++.h>
#define _EXT_CODECVT_SPECIALIZATIONS_H 1
#define _EXT_ENC_FILEBUF_H 1
using namespace std;
#pragma GCC diagnostic ignored "-Wparentheses"
#define SYSCALL_ALLOWED 1
#if SYSCALL_ALLOWED
#include <bits/extc++.h>
#include <ext/rope>
#endif
using fp = double;
using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using pint = pair<i64, i64>;
using tint = tuple<i64, i64, i64>;
template <class T>
using Str = basic_string<T>;
template <class T, class CMP = less<>>
using PQ = std::priority_queue<T, vector<T>, CMP>;
template <class T>
i64 sz(const T& x) {
return x.size();
}
i64 fdiv(i64 a, i64 b) {
if (b < 0) a = -a, b = -b;
return (a > 0) ? a / b : (a - b + 1) / b;
}
i64 cdiv(i64 a, i64 b) {
if (b < 0) a = -a, b = -b;
return (a > 0) ? (a + b - 1) / b : a / b;
}
i64 flg2(u64 x) { return 63 - __builtin_clzll(x); }
i64 clg2(u64 x) { return x - 1 == 0 ? 0 : 64 - __builtin_clzll(x - 1); }
i64 fsqrt(i64 n) {
i64 i = 0;
while (i * i <= n) i++;
return i - 1;
}
i64 csqrt(i64 n) {
i64 i = 0;
while (i * i < n) i++;
return i;
}
template <class T>
T sq(T x) {
return x * x;
}
template <class T>
constexpr T inf() {
return numeric_limits<T>::max() / 2;
}
template <class... A>
ostream& osprint(ostream& os, A... a) {
return ((os << a), ...);
}
template <class T, class U>
bool assmin(T& a, U&& b) {
return a > b ? a = b, true : false;
}
template <class T, class U>
bool assmax(T& a, U&& b) {
return a < b ? a = b, true : false;
}
auto key2cmp(auto key) {
return [key](auto x, auto y) {
return make_pair(key(x), x) < make_pair(key(y), y);
};
}
template <class T, class P = vector<T>>
struct Arr : public P {
Arr() { P::shrink_to_fit(); }
explicit Arr(signed n) : P(n) {}
explicit Arr(signed n, T init) : P(n, init) {}
Arr(initializer_list<T> il) : P(il) {}
Arr(auto its, auto ite) : P(its, ite) {}
inline T& operator[](signed i) {
assert(-sz(*this) <= i && i < sz(*this));
return P::operator[](i < 0 ? i + sz(*this) : i);
}
const T& operator[](signed i) const {
assert(-sz(*this) <= i && i < sz(*this));
return P::operator[](i < 0 ? i + sz(*this) : i);
}
T& at(signed i) { return *this[i]; }
const T& at(signed i) const { return *this[i]; }
};
template <class... A>
auto ARR(auto n, A&&... a) {
if constexpr (!sizeof...(a))
return n;
else
return Arr(n, ARR(a...));
}
const fp pi = acos(-1), eps = 1e-11;
const i64 dir4[4][2] = {{0, 1}, {-1, 0}, {0, -1}, {1, 0}};
const i64 dir8[8][2] = {{0, 1}, {-1, 1}, {-1, 0}, {-1, -1},
{0, -1}, {1, -1}, {1, 0}, {1, 1}};
template <class T>
i64 argmin(const Arr<T>& a) {
return min_element(a.begin(), a.end()) - a.begin();
}
template <class T>
i64 argmax(const Arr<T>& a) {
return max_element(a.begin(), a.end()) - a.begin();
}
template <class T>
map<typename T::value_type, Arr<i64>> classify(const T& a) {
map<typename T::value_type, Arr<i64>> r;
i64 idx = 0;
for (auto x : a) r[x].push_back(idx++);
return r;
}
auto __PR = (cout << fixed << setprecision(10), 0);
auto __PR_NDB = (ios::sync_with_stdio(0), cin.tie(0), cout.tie(0));
struct LeftHull {
void pf_dec(i64 x) { pq.push(x - bias); }
i64 sf_inc(i64 x) {
if (pq.empty() or argmin() <= x) return x;
ans += argmin() - x;
pq.push(x - bias);
i64 r = argmin();
pq.pop();
return r;
}
void add_bias(i64 x, i64 y) {
bias += x;
ans += y;
}
i64 minval() { return ans; }
i64 argmin() { return pq.empty() ? -inf<i64>() : pq.top() + bias; }
void operator+=(LeftHull& a) {
ans += a.ans;
while (sz(a.pq)) pf_dec(a.argmin()), a.pq.pop();
}
i64 size() const { return sz(pq); }
i64 pop() {
i64 z = argmin();
pq.pop();
return z;
}
private:
PQ<i64, less<>> pq;
i64 ans = 0, bias = 0;
};
struct RightHull {
void pf_dec(i64 x) { r.sf_inc(-x); }
void sf_inc(i64 x) { r.pf_dec(-x); }
void add_bias(i64 x, i64 y) { r.add_bias(-x, y); }
i64 minval() { return r.minval(); }
i64 argmin() { return -r.argmin(); }
void operator+=(RightHull& a) { r += a.r; }
i64 size() const { return r.size(); }
LeftHull r;
};
struct SlopeTrick {
void pf_dec(i64 x) { l.pf_dec(-r.sf_inc(-x)); }
void sf_inc(i64 x) { r.pf_dec(-l.sf_inc(x)); }
void add_bias(i64 lx, i64 rx, i64 y) {
l.add_bias(lx, 0), r.add_bias(-rx, 0), ans += y;
}
i64 minval() { return ans + l.minval() + r.minval(); }
pint argmin() { return {l.argmin(), -r.argmin()}; }
void operator+=(SlopeTrick& a) {
ans += a.ans;
while (sz(a.l)) pf_dec(a.l.pop());
l.add_bias(0, a.l.minval());
while (sz(a.r)) sf_inc(-a.r.pop());
r.add_bias(0, a.r.minval());
}
i64 size() const { return l.size() + r.size(); }
LeftHull l, r;
i64 ans = 0;
};
struct LeftHullMap {
void pf_dec(i64 x, i64 k) { a[x - bias] += k; }
Arr<pint> sf_inc(i64 x, i64 k) {
Arr<pint> ret;
while (k and argmin() > x) {
i64 cnt = min(mincnt(), k);
ans += (argmin() - x) * cnt;
a[x - bias] += cnt;
ret.emplace_back(argmin(), cnt);
pop(cnt);
k -= cnt;
}
if (k) ret.emplace_back(x, k);
return ret;
}
void add_bias(i64 x, i64 y) {
bias += x;
ans += y;
}
i64 minval() { return ans; }
i64 argmin() { return a.empty() ? -inf<i64>() : prev(a.end())->first + bias; }
i64 mincnt() { return a.empty() ? 0 : a[argmin() - bias]; }
void operator+=(LeftHullMap& a) {
ans += a.ans;
while (sz(a.a)) pf_dec(a.argmin(), a.mincnt()), a.a.erase(prev(a.a.end()));
}
i64 size() const { return sz(a); }
Arr<pint> pop(i64 k) {
Arr<pint> ret;
while (k and sz(a)) {
i64 c = min(k, prev(a.end())->second);
k -= c;
ret.emplace_back(argmin(), c);
if ((prev(a.end())->second -= c) == 0) a.erase(prev(a.end()));
}
return ret;
}
private:
map<i64, i64> a;
i64 ans = 0, bias = 0;
};
struct SlopeTrickMap {
void pf_dec(i64 x, i64 k) {
for (auto [x2, k2] : r.sf_inc(-x, k)) l.pf_dec(-x2, k2);
}
void sf_inc(i64 x, i64 k) {
for (auto [x2, k2] : l.sf_inc(x, k)) r.pf_dec(-x2, k2);
}
void add_bias(i64 lx, i64 rx, i64 y) {
l.add_bias(lx, 0), r.add_bias(-rx, 0), ans += y;
}
i64 minval() { return ans + l.minval() + r.minval(); }
pint argmin() { return {l.argmin(), -r.argmin()}; }
void operator+=(SlopeTrickMap& a) {
ans += a.ans;
for (auto [x, k] : a.l.pop(inf<i64>())) pf_dec(x, k);
l.add_bias(0, a.l.minval());
for (auto [x, k] : a.r.pop(inf<i64>())) sf_inc(-x, k);
r.add_bias(0, a.r.minval());
}
i64 size() const { return l.size() + r.size(); }
LeftHullMap l, r;
i64 ans = 0;
};
struct SlopeTrick1der {
void add(i64 x) { pq.push(x); }
PQ<i64, less<i64>> pq;
};
signed main() {
void solve();
solve();
assert(cin.get() == '\n');
assert(cin.get() == EOF);
}
void solve() {
i64 n;
cin >> n;
Arr<i64> a(n);
for (i64 i = 0; i < n; i++) {
i64 x, y;
cin >> x >> y;
a[i] = x - y;
}
Arr<i64> b(n + 1);
partial_sum(a.begin(), a.end(), b.begin());
LeftHull z;
for (i64 i = 0; i < n; i++) {
z.pf_dec(max(0ll, b[i]));
z.sf_inc(min(b[n - 1], b[i]));
}
osprint(cout, z.minval(), '\n');
}
Compilation message (stderr)
bulves.cpp:116:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
116 | auto key2cmp(auto key) {
| ^~~~
bulves.cpp:127:7: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
127 | Arr(auto its, auto ite) : P(its, ite) {}
| ^~~~
bulves.cpp:127:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
127 | Arr(auto its, auto ite) : P(its, ite) {}
| ^~~~
bulves.cpp:140:10: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
140 | auto ARR(auto n, A&&... a) {
| ^~~~
# | 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... |