Submission #737214

#	Time	Username	Problem	Language	Result	Execution time	Memory
737214		lobo_prix	Potatoes and fertilizers (LMIO19_bulves)	C++17	0 / 100	0 ms	212 KiB

bulves

//[Author]   tuxedcat
//[Date]     2023.05.07 07:00:08 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());

	SlopeTrick z;
	for(int i=0;i<n;i++){
		z.pf_dec(b[i]);
		z.sf_inc(b[i]);
		z.add_bias(0,1000000,0);
	}
	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 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());
  SlopeTrick z;
  for (i64 i = 0; i < n; i++) {
    z.pf_dec(b[i]);
    z.sf_inc(b[i]);
    z.add_bias(0, 1000000, 0);
  }
  osprint(cout, z.minval(), '\n');
}

Compilation message (stderr)

bulves.cpp:114:14: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  114 | auto key2cmp(auto key) {
      |              ^~~~
bulves.cpp:125:7: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  125 |   Arr(auto its, auto ite) : P(its, ite) {}
      |       ^~~~
bulves.cpp:125:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  125 |   Arr(auto its, auto ite) : P(its, ite) {}
      |                 ^~~~
bulves.cpp:138:10: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
  138 | auto ARR(auto n, A&&... a) {
      |          ^~~~

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