Submission #737835

#TimeUsernameProblemLanguageResultExecution timeMemory
737835lobo_prixPotatoes and fertilizers (LMIO19_bulves)C++17
100 / 100
191 ms19244 KiB
//[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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...