oj.uz

Submission #737835

# Submission time Handle Problem Language Result Execution time Memory
737835 2023-05-07T19:57:22 Z lobo_prix Potatoes and fertilizers (LMIO19_bulves) C++17
100 / 100
 191 ms 19244 KB 
//[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

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) {
      |          ^~~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 12 ms 2000 KB Output is correct
5 Correct 21 ms 3688 KB Output is correct
6 Correct 58 ms 9668 KB Output is correct
7 Correct 127 ms 19132 KB Output is correct
8 Correct 103 ms 17252 KB Output is correct
9 Correct 107 ms 16492 KB Output is correct
10 Correct 77 ms 14244 KB Output is correct
11 Correct 82 ms 14268 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 12 ms 2000 KB Output is correct
5 Correct 21 ms 3688 KB Output is correct
6 Correct 58 ms 9668 KB Output is correct
7 Correct 127 ms 19132 KB Output is correct
8 Correct 103 ms 17252 KB Output is correct
9 Correct 107 ms 16492 KB Output is correct
10 Correct 77 ms 14244 KB Output is correct
11 Correct 82 ms 14268 KB Output is correct
12 Correct 34 ms 4992 KB Output is correct
13 Correct 75 ms 13260 KB Output is correct
14 Correct 124 ms 19056 KB Output is correct
15 Correct 102 ms 17224 KB Output is correct
16 Correct 100 ms 16492 KB Output is correct
17 Correct 65 ms 14320 KB Output is correct
18 Correct 1 ms 340 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 1 ms 460 KB Output is correct
15 Correct 2 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 460 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 12 ms 2000 KB Output is correct
12 Correct 21 ms 3688 KB Output is correct
13 Correct 58 ms 9668 KB Output is correct
14 Correct 127 ms 19132 KB Output is correct
15 Correct 103 ms 17252 KB Output is correct
16 Correct 107 ms 16492 KB Output is correct
17 Correct 77 ms 14244 KB Output is correct
18 Correct 82 ms 14268 KB Output is correct
19 Correct 34 ms 4992 KB Output is correct
20 Correct 75 ms 13260 KB Output is correct
21 Correct 124 ms 19056 KB Output is correct
22 Correct 102 ms 17224 KB Output is correct
23 Correct 100 ms 16492 KB Output is correct
24 Correct 65 ms 14320 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 1 ms 460 KB Output is correct
28 Correct 2 ms 340 KB Output is correct
29 Correct 2 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 460 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 32 ms 5116 KB Output is correct
34 Correct 82 ms 13244 KB Output is correct
35 Correct 137 ms 19060 KB Output is correct
36 Correct 125 ms 16620 KB Output is correct
37 Correct 105 ms 17212 KB Output is correct
38 Correct 133 ms 19056 KB Output is correct
39 Correct 93 ms 15208 KB Output is correct
40 Correct 89 ms 14452 KB Output is correct
41 Correct 83 ms 14324 KB Output is correct
42 Correct 72 ms 14312 KB Output is correct
43 Correct 78 ms 14396 KB Output is correct
44 Correct 77 ms 14316 KB Output is correct
45 Correct 191 ms 19244 KB Output is correct
46 Correct 66 ms 14652 KB Output is correct
47 Correct 80 ms 13232 KB Output is correct