#844452 (C++17) No.1467 Selling Cars

提出ソース
結果

問題	No.1467 Selling Cars
コンテスト
ユーザー	hashiryo
提出日時	2023-02-27 20:33:54
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	1,100 ms / 4,000 ms
コード長	17,192 bytes
コンパイル時間	3,600 ms
コンパイル使用メモリ	226,584 KB
最終ジャッジ日時	2025-02-10 23:57:41
ジャッジサーバーID （参考情報）	judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 31
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
// clang-format off
std::ostream&operator<<(std::ostream&os,std::int8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,std::uint8_t x){return os<<(int)x;}
std::ostream&operator<<(std::ostream&os,const __int128_t &v){if(!v)os<<"0";__int128_t tmp=v<0?(os<<"-",-v):v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}
std::ostream&operator<<(std::ostream&os,const __uint128_t &v){if(!v)os<<"0";__uint128_t tmp=v;std::string s;while(tmp)s+='0'+(tmp%10),tmp/=10;return std::reverse(s.begin(),s.end()),os<<s;}

#define checkpoint() (void(0))
#define debug(x) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// clang-format on
#ifdef __LOCAL
// clang-format off
#undef checkpoint
#undef debug
#undef debugArray
#undef debugMatrix
template<class T, class U>std::ostream &operator<<(std::ostream&os,const std::pair<T,U>&x){return os<<"("<<x.first<<", "<<x.second<<")";}
template<typename T>std::ostream &operator<<(std::ostream&os,const std::vector<T>&vec){os<<'[';for(int _=0,__= vec.size();_<__;++_)os<<(_ ?", ":"")<<vec[_];return os<<']';}
template<typename T>std::ostream &operator<<(std::ostream&os,const std::set<T>&s){os<<'{';int _=0;for(const auto &x:s)os<<(_++ ? ", " : "")<<x; return os << '}';}
template<typename T,std::size_t _Nm>std::ostream&operator<<(std::ostream &os,const std::array<T, _Nm> &arr) {os<<'['<<arr[0];for(std::size_t _=1;_<_Nm;++_)os<<", "<<arr[_];return os<<']';}
template<class Tup,std::size_t... I>void print(std::ostream&os,const Tup &x,std::index_sequence<I...>){(void)(int[]){(os<<std::get<I>(x)<<", ",0)...};}
template<class... Args>std::ostream &operator<<(std::ostream&os,const std::tuple<Args...> &x) {static constexpr std::size_t N = sizeof...(Args);os<<"(";if constexpr(N>=2)print(os,x,std::make_index_sequence<N-1>());return os<<std::get<N-1>(x)<<")";}
const std::string COLOR_RESET="\033[0m",BRIGHT_GREEN="\033[1;32m",BRIGHT_RED="\033[1;31m",BRIGHT_CYAN="\033[1;36m",NORMAL_CROSSED="\033[0;9;37m",ITALIC="\033[3m",BOLD="\033[1m",RED_BACKGROUND="\033[1;41m",NORMAL_FAINT="\033[0;2m";
#define func_LINE_FILE  NORMAL_FAINT<<" in "<<BOLD<<__func__<<NORMAL_FAINT<<ITALIC<<" (L"<<__LINE__<<") "<< __FILE__<<COLOR_RESET
#define checkpoint() std::cerr<<BRIGHT_RED<<"< check point! >"<<func_LINE_FILE<<'\n'
#define debug(x) std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = "<<(x)<<func_LINE_FILE<<'\n'
#define debugArray(x, n) do{std::cerr<<BRIGHT_CYAN<<#x<<COLOR_RESET<<" = ["<<x[0];for(int _=1;_<(int)(n);++_)std::cerr<<", "<<x[_];std::cerr<<"]"<<func_LINE_FILE<<'\n';}while(0)
#define debugMatrix(x, h, w) do{std::cerr<<BRIGHT_CYAN<<#x<<"\n"<<COLOR_RESET<<"= ";for(int _=0;(_)<(int)(h);++_){std::cerr<<((_?"   [":"[["));for(int __=0;__<(int)(w);++__)std::cerr<<((__?", ":""))<<x[_][__];std::cerr<<"]"<<(_+1==(int)(h)?"]":",\n");}std::cerr<<func_LINE_FILE<<'\n';}while(0)
#endif
// clang-format on
template <class T> auto compress(std::vector<T> &v) {
 return std::sort(v.begin(), v.end()), v.erase(std::unique(v.begin(), v.end()), v.end()), [&v](T x) { return std::lower_bound(v.begin(), v.end(), x) - v.begin(); };
}
class CartesianTree {
 std::vector<std::array<int, 2>> rg, ch;
 std::vector<int> par;
 int rt;
public:
 template <class T> CartesianTree(const std::vector<T> &a, bool is_min= 1): rg(a.size()), ch(a.size(), std::array{-1, -1}), par(a.size(), -1) {
  const int n= a.size();
  auto comp= [&](int l, int r) { return (is_min ? a[l] < a[r] : a[l] > a[r]) || (a[l] == a[r] && l < r); };
  std::vector<int> st;
  st.reserve(n);
  for (int i= 0; i < n; rg[i][0]= (st.empty() ? 0 : st.back() + 1), st.push_back(i++))
   for (; !st.empty() && comp(i, st.back()); st.pop_back()) ch[i][0]= st.back();
  st.clear();
  for (int i= n; i--; rg[i][1]= (st.empty() ? n : st.back()), st.push_back(i))
   for (; !st.empty() && comp(i, st.back()); st.pop_back()) ch[i][1]= st.back();
  for (int i= 0; i < n; ++i)
   for (int b= 2; b--;)
    if (ch[i][b] != -1) par[ch[i][b]]= i;
  for (int i= 0; i < n; ++i)
   if (par[i] == -1) rt= i;
 }
 std::array<int, 2> children(int i) const { return ch[i]; }
 int parent(int i) const { return par[i]; }
 int root() const { return rt; }
 // [l,r)
 std::array<int, 2> range(int i) const { return rg[i]; }
};
template <std::size_t NODE_SIZE= 1 << 22> class PiecewiseLinearConvexfunction {
public:
 using i64= long long;
 using i128= __int128_t;
 using node_id= std::int_least32_t;
 static constexpr i64 INF= 1ll << 41;
 template <class Int> static inline std::string str(Int x) {
  if (x >= INF) return "inf";
  if (x <= -INF) return "-inf";
  std::stringstream ss;
  ss << x;
  return ss.str();
 }
 struct Node {
  node_id ch[2], par;
  int sz;
  i64 dx, slope, laz, x;
  i128 y;
 };
 friend std::ostream &operator<<(std::ostream &os, Node *t) {
  if (!t) return os << "nullptr";
  return os << "{dx:" << str(t->dx) << ",slope:" << str(t->slope) << ",x:" << str(t->x) << ",y:" << str(t->y) << ",laz:" << str(t->laz) << "}";
 }
 // friend std::ostream &operator<<(std::ostream &os, Node *t) {
 //  if (!t) return os << "nullptr";
 //  return os << "{dx:" << str(t->dx) << ",slope:" << str(t->slope) << "}";
 // }
 static inline Node ns[NODE_SIZE];
 static inline node_id ni= 1;
 static inline node_id new_node() { return ni++; }
 static inline node_id new_node(i64 dx, i64 slope) { return ns[ni].ch[0]= ns[ni].ch[1]= ns[ni].par= ns[ni].laz= 0, ns[ni].y= i128(ns[ni].x= ns[ni].dx= dx) * (ns[ni].slope= slope), ns[ni].sz= 1, ni++; }
 static inline void propagate(node_id i, i64 a) {
  if (i) ns[i].slope+= a, ns[i].laz+= a, ns[i].y+= i128(a) * ns[i].x;
 }
 static inline void push(node_id i) {
  if (ns[i].laz) propagate(ns[i].ch[0], ns[i].laz), propagate(ns[i].ch[1], ns[i].laz), ns[i].laz= 0;
 }
 static inline void pushup(node_id i) {
  ns[i].sz= 1, ns[i].x= ns[i].dx, ns[i].y= i128(ns[i].slope) * ns[i].dx;
  if (int j= ns[i].ch[0]; j) ns[i].sz+= ns[j].sz, ns[i].x+= ns[j].x, ns[i].y+= ns[j].y;
  if (int j= ns[i].ch[1]; j) ns[i].sz+= ns[j].sz, ns[i].x+= ns[j].x, ns[i].y+= ns[j].y;
 }
 static inline int dir(node_id i) { return ns[ns[i].par].ch[1] == i; }
 static inline void rot(node_id i) {
  node_id p= ns[i].par;
  int d= dir(i);
  if ((ns[p].ch[d]= ns[i].ch[!d])) ns[ns[p].ch[d]].par= p;
  ns[i].ch[!d]= p;
  if ((ns[i].par= ns[p].par)) ns[ns[p].par].ch[dir(p)]= i;
  ns[p].par= i;
 }
 static inline void splay(node_id i) {
  for (node_id p= ns[i].par; p; p= ns[i].par) {
   if (node_id pp= ns[p].par; pp) rot(dir(i) == dir(p) ? p : i), rot(i), pushup(pp), pushup(p);
   else rot(i), pushup(p);
  }
  pushup(i);
 }
 static inline void slope_search(node_id &i, i64 k) {
  for (node_id s;; i= s) {
   push(i);
   i64 tmp= ns[i].slope;
   if (tmp == k) break;
   if (s= ns[i].ch[tmp < k]; !s) break;
  }
  splay(i);
 }
 static inline void x_search(node_id &i, i64 x) {
  for (bool c;; i= ns[i].ch[c]) {
   push(i);
   i64 l= ns[i].ch[0] ? ns[ns[i].ch[0]].x : 0, r= l + ns[i].dx;
   if (l <= x && x <= r) return splay(i);
   if ((c= (r < x))) x-= r;
  }
 }
 static inline void add(node_id i, i64 &x, i64 &p, PiecewiseLinearConvexfunction &f) {
  if (!i) return;
  push(i);
  add(ns[i].ch[0], x, p, f);
  f.add_ax_bx_c(0, ns[i].slope - p, x);
  x+= ns[i].dx, p= ns[i].slope;
  add(ns[i].ch[1], x, p, f);
 }
 static inline void debugoutput(node_id i, int d) {
  if (!i) return;
  push(i);
  debugoutput(ns[i].ch[0], d + 1);
  for (int i= 0; i < d; ++i) std::cerr << "   ";
  std::cerr << "■ " << (i ? ns + i : nullptr) << '\n';
  debugoutput(ns[i].ch[1], d + 1);
 }
 node_id root;
 i64 lx, lslope;
 i128 ly;
public:
 static inline void clear() { ni= 1; }
 void debugoutput() { debugoutput(root, 0); }
 i64 upper_bound() { return lx + (root ? ns[root].x : 0); }
 // f(x) := 0
 PiecewiseLinearConvexfunction(): root(0), lx(INF * 2), lslope(0), ly(0) {}
 // f(x) + c
 void add_const(i128 c) { ly+= c; }
 // f(x) + ax+c
 void add_linear(i64 a, i128 c= 0) { lslope+= a, ly+= i128(a) * lx + c, propagate(root, a); }
 // f(x-a)
 void shift(i64 a) { lx+= a; }
 // f(x) + a * max{x-c, 0}
 void add_relu(i64 a, i64 c) {
  if (!a) return;
  assert(a > 0);
  if (c < lx) {
   if (lslope < -INF) return add_linear(a, -i128(a) * c);
   node_id i= new_node(lx - c, lslope);
   if (root) x_search(root, 0), ns[root].ch[0]= i, ns[i].par= root, pushup(root);
   else root= i;
   ly-= ns[i].y, lx= c, propagate(root, a);
   return;
  }
  if (upper_bound() <= c) return;
  c-= lx, x_search(root, c);
  i64 l= ns[root].ch[0] ? ns[ns[root].ch[0]].x : 0, r= l + ns[root].dx;
  if (l == c) {
   node_id i= ns[root].ch[0];
   ns[root].ch[0]= 0, propagate(root, a), push(root), ns[root].ch[0]= i;
  } else if (r == c) {
   propagate(ns[root].ch[1], a);
  } else {
   node_id i= new_node(r - c, ns[root].slope);
   if ((ns[i].ch[1]= ns[root].ch[1])) ns[ns[i].ch[1]].par= i;
   pushup(i), propagate(i, a), ns[root].ch[1]= i, ns[i].par= root, ns[root].dx= c - l, pushup(root);
  }
 }
 // f(x) + a * min{x-c,0} + b * max{x-c,0}
 void add_ax_bx_c(i64 a, i64 b, i64 c) { assert(a <= b), add_linear(a, -i128(a) * c), add_relu(b - a, c); }
 // f(x) + a * |x-c|
 void add_abs(i64 a, i64 c) { add_ax_bx_c(-a, a, c); }
 // ∞ if x>a else f(x)
 void chinfty_right(i64 a= 0) {
  assert(lx <= a || lslope >= -INF);
  if (root) {
   if (a-= lx; ns[root].x <= a) return;
   x_search(root, a);
   i64 l= ns[root].ch[0] ? ns[ns[root].ch[0]].x : 0;
   if (l == a) root= ns[root].ch[0], ns[root].par= 0;
   else ns[root].dx= a - l, ns[root].ch[1]= 0, pushup(root);
  } else lx= a;
 }
 // ∞ if x<a else f(x)
 void chinfty_left(i64 a= 0) {
  assert(a <= upper_bound());
  if (a-= lx; a < 0) {
   if (lslope < -INF) return;
   node_id i= new_node(-a, lslope);
   if (root) x_search(root, 0), ns[root].ch[0]= i, ns[i].par= root, pushup(root);
   else root= i;
   ly-= ns[i].y;
  } else if (a > 0) {
   assert(root);
   x_search(root, a);
   i64 r= ns[root].dx;
   if (int i= ns[root].ch[0]; i) ly+= ns[i].y + i128(a - ns[i].x) * ns[root].slope, r+= ns[i].x;
   else ly+= i128(a) * ns[root].slope;
   if (r == a) root= ns[root].ch[1], ns[root].par= 0;
   else ns[root].dx= r - a, ns[root].ch[0]= 0, pushup(root);
  }
  lx+= a, lslope= -INF * 2;
 }
 // min_{y<=x} f(y)
 void cumulative_chmin() {
  assert(lslope <= 0);
  if (root) {
   slope_search(root, 0);
   if (ns[root].slope < 0) {
    if (!ns[root].ch[1]) ns[root].ch[1]= new_node();
    node_id i= ns[root].ch[1];
    ns[i].sz= 1, ns[i].x= ns[i].dx= INF * 2, ns[i].slope= ns[i].ch[0]= ns[i].ch[1]= ns[i].laz= ns[i].y= 0, ns[i].par= root;
   } else ns[root].ch[1]= 0, ns[root].dx= INF * 2, ns[root].slope= 0;
   pushup(root);
  } else if (lslope) root= new_node(INF * 2, 0);
  else lx= INF * 2;
 }
 // min_{y>=x} f(y)
 void cumulative_chmin_rev() {
  if (root) {
   slope_search(root, 0);
   i64 l= ns[root].ch[0] ? ns[ns[root].ch[0]].x : 0, r= l + ns[root].dx, x= ns[root].slope > 0 ? l : r;
   if (int i= ns[root].ch[0]; i) ly+= ns[i].y + i128(x - ns[i].x) * ns[root].slope;
   else ly+= i128(x) * ns[root].slope;
   if (ns[root].slope > 0) ns[root].ch[0]= 0, pushup(root);
   else root= ns[root].ch[1], ns[root].par= 0;
   lx+= x;
  }
  lslope= 0;
 }
 // min_{y>=x ∧ y>=a} f(y)
 void cumulative_chmin_rev_with_condition(i64 a) {
  if (a-= lx; a < 0) {
   if (lslope <= 0) return cumulative_chmin_rev();
   node_id i= new_node(-a, lslope);
   if (root) x_search(root, 0), ns[root].ch[0]= i, ns[i].par= root, pushup(root);
   else root= i;
   ly-= ns[i].y;
  } else {
   assert(root), assert(a < ns[root].x);
   x_search(root, a);
   if (ns[root].slope <= 0) return cumulative_chmin_rev();
   i64 r= ns[root].dx;
   if (int i= ns[root].ch[0]; i) ly+= ns[i].y + i128(a - ns[i].x) * ns[root].slope, r+= ns[i].x;
   else ly+= i128(a) * ns[root].slope;
   if (r == a) root= ns[root].ch[1], ns[root].par= 0;
   else ns[root].dx= r - a, ns[root].ch[0]= 0, pushup(root);
  }
  lx+= a, lslope= 0;
 }
 // min_{x-a<=y<=x} f(y)
 void chmin_sliding_window(i64 a) {
  if (!a) return;
  assert(a > 0);
  if (root) {
   slope_search(root, 0);
   if (ns[root].slope) {
    node_id i= new_node(a, 0);
    bool c= ns[root].slope < 0;
    if ((ns[i].ch[c]= ns[root].ch[c])) ns[ns[i].ch[c]].par= i;
    pushup(i), ns[root].ch[c]= i, ns[i].par= root;
   } else ns[root].dx+= a;
   pushup(root);
  } else if (lslope >= 0) lx+= a;
  else root= new_node(a, 0);
 }
 // min_{x-b<=y<=x-a} f(y)
 void chmin_sliding_window(i64 a, i64 b) { assert(a <= b), shift(a), chmin_sliding_window(b - a); }
 i128 eval(i64 x) {
  if (x < lx && lslope < -INF) return INF;
  if (x <= lx) return ly + i128(x - lx) * lslope;
  if (!root) return INF;
  if (x-= lx; ns[root].x < x) return INF;
  x_search(root, x);
  if (int i= ns[root].ch[0]; i) return ly + ns[i].y + i128(x - ns[i].x) * ns[root].slope;
  return ly + i128(x) * ns[root].slope;
 }
 std::array<i64, 2> argmin() {
  assert(lslope <= 0);
  if (!lslope) return std::array{-INF, lx};
  if (!root) return std::array{lx, lx};
  slope_search(root, 0);
  i64 l= lx + (ns[root].ch[0] ? ns[ns[root].ch[0]].x : 0), r= l + ns[root].dx;
  if (ns[root].slope == 0) return {l, r};
  return ns[root].slope < 0 ? std::array{r, r} : std::array{l, l};
 }
 i128 min() { return eval(argmin()[1]); }
 int size() { return root ? ns[root].sz : 0; }
 // destructive
 PiecewiseLinearConvexfunction operator+(PiecewiseLinearConvexfunction &r) {
  if (size() > r.size()) std::swap(*this, r);
  if (lslope < -INF) r.chinfty_left(lx);
  else r.add_ax_bx_c(lslope, 0, lx);
  r.chinfty_right(upper_bound());
  long long x= lx, p= 0;
  add(root, x, p, r), r.add_const(ly);
  return r;
 }
 // destructive
 PiecewiseLinearConvexfunction &operator+=(PiecewiseLinearConvexfunction &r) { return *this= *this + r; }
};
using namespace std;
// https://atcoder.jp/contests/abc127/tasks/abc127_f
namespace ABC127F {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int Q;
 cin >> Q;
 PiecewiseLinearConvexfunction f;
 while (Q--) {
  int op;
  cin >> op;
  if (op == 1) {
   int a, b;
   cin >> a >> b;
   f.add_abs(1, a);
   f.add_const(b);
  } else {
   cout << f.argmin()[0] << " " << f.min() << '\n';
  }
 }
 return 0;
}
}
// https://atcoder.jp/contests/kupc2016/tasks/kupc2016_h
namespace atcoder_kupc2016_h {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 long long A[N], B[N];
 for (int i= 0; i < N; ++i) cin >> A[i];
 for (int i= 0; i < N; ++i) cin >> B[i];
 PiecewiseLinearConvexfunction f;
 f.chinfty_left();
 for (int i= 0; i < N; ++i) {
  f.cumulative_chmin();
  f.shift(B[i] - A[i]);
  if (i < N - 1) f.add_abs(1, 0);
 }
 cout << f.eval(0) << '\n';
 return 0;
}
}
// https://atcoder.jp/contests/abc250/tasks/abc250_g
namespace ABC250G_Conj {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 PiecewiseLinearConvexfunction f;
 for (int i= 0; i < N; ++i) {
  int P;
  cin >> P;
  f.add_ax_bx_c(-1, 1, P);
  f.cumulative_chmin_rev();
 }
 cout << f.eval(0) << '\n';
 return 0;
}
}
// https://atcoder.jp/contests/utpc2012/tasks/utpc2012_12
namespace atcoder_utpc2012_12 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, C;
 cin >> N >> C;
 vector<vector<int>> tree(N);
 vector<PiecewiseLinearConvexfunction<>> dp(N);
 dp[0].add_abs(1, C);
 for (int i= 1, P; i < N; i++) cin >> P >> C, tree[--P].push_back(i), dp[i].add_abs(1, C);
 auto dfs= [&tree, &dp](auto self, int v) -> void {
  for (int u: tree[v]) self(self, u), dp[u].cumulative_chmin(), dp[u].shift(1), dp[v]+= dp[u];
 };
 dfs(dfs, 0);
 cout << dp[0].min() << '\n';
 return 0;
}
}
// https://atcoder.jp/contests/abc275/tasks/abc275_h
namespace ABC275Ex {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 vector<int> A(N), B(N);
 for (int i= 0; i < N; ++i) cin >> A[i];
 for (int i= 0; i < N; ++i) cin >> B[i];
 CartesianTree ct(B, false);
 int root= ct.root();
 vector<PiecewiseLinearConvexfunction<>> dp(N);
 auto dfs= [&](auto self, int v) -> void {
  for (int u: ct.children(v))
   if (u != -1) {
    self(self, u);
    dp[v]+= dp[u];
   }
  dp[v].add_linear(B[v]);
  dp[v].cumulative_chmin_rev_with_condition(A[v]);
  dp[v].add_linear(-B[v]);
 };
 dfs(dfs, root);
 cout << dp[root].eval(0) << '\n';
 return 0;
}
}
// https://yukicoder.me/problems/no/1467
namespace yukicoder1467 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 using PLCF= PiecewiseLinearConvexfunction<>;
 int M, N;
 cin >> M >> N;
 long long A[M], B[N];
 for (int i= 0; i < M; ++i) cin >> A[i];
 for (int j= 0; j < N; ++j) cin >> B[j];
 vector<long long> vec(A, A + M);
 for (int j= 0; j < N; ++j) vec.push_back(B[j]);
 auto id= compress(vec);
 int n= vec.size();
 vector<long long> a(n), b(n);
 for (int i= 0; i < M; ++i) ++a[id(A[i])];
 for (int j= 0; j < N; ++j) ++b[id(B[j])];
 for (int k= 1; k <= M; ++k) {
  PLCF f;
  f.chinfty_left();
  for (int i= 0; i < n; ++i) {
   f.cumulative_chmin();
   f.shift(a[i] - b[i] * k);
   if (i < n - 1) f.add_abs(vec[i + 1] - vec[i], 0);
  }
  cout << f.eval(0) << '\n';
  PLCF::clear();
 }
 return 0;
}
}
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 // ABC127F::main();
 // atcoder_kupc2016_h::main();
 // ABC250G_Conj::main();
 // atcoder_utpc2012_12::main();
 // ABC275Ex::main();
 yukicoder1467::main();
 return 0;
}