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

提出ソース
結果

問題	No.1467 Selling Cars
コンテスト
ユーザー	hashiryo
提出日時	2023-02-18 14:51:30
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	TLE
実行時間	-
コード長	13,237 bytes
コンパイル時間	2,965 ms
コンパイル使用メモリ	224,388 KB
最終ジャッジ日時	2025-02-10 18:52:22
ジャッジサーバーID （参考情報）	judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 7 TLE * 7 MLE * 17
権限があれば一括ダウンロードができます
ソースコード

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 PiecewiseLinearConvexfunction {
public:
 using i64= long long;
 using i128= __int128_t;
 static constexpr i64 INF= 1ll << 60;
 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 *ch[2]= {nullptr, nullptr}, *par= nullptr;
  i64 dat[2]= {0, 0}, laz[2]= {0, 0};
  bool flg= false;
  int sz= 0;
  i64 sum[2]= {0, 0};
  i128 psum= 0;
 };
 // friend std::ostream &operator<<(std::ostream &os, Node *t) {
 //  if (!t) return os << "nullptr";
 //  return os << "{dat[2]:(" << str(t->dat[0]) << "," << str(t->dat[1]) << "), laz[2]:(" << str(t->laz[0]) << "," << str(t->laz[1]) << "), flg:" << t->flg << ", sz:" << t->sz << ", sum[2]:(" << str(t->sum[0]) << "," << str(t->sum[2]) << "), psum:" << str(t->psum) << "}";
 // }
 friend std::ostream &operator<<(std::ostream &os, Node *t) {
  if (!t) return os << "nullptr";
  return os << "(" << str(t->dat[0]) << "," << str(t->dat[1]) << ")";
 }
 static inline void propagate(Node *t, const i64 x[2]) {
  if (!t) return;
  if (x[0]) {
   t->dat[0]+= x[0], t->laz[0]+= x[0];
   t->psum+= (i128)(t->sum[1]) * x[0];
   t->sum[0]+= x[0] * t->sz;
  }
  if (x[1]) {
   t->dat[1]+= x[1], t->laz[1]+= x[1];
   t->psum+= (i128)(t->sum[0]) * x[1];
   t->sum[1]+= x[1] * t->sz;
  }
 }
 static inline void eval(Node *t) { propagate(t->ch[0], t->laz), propagate(t->ch[1], t->laz), t->laz[0]= t->laz[1]= 0; }
 static inline void add_(Node *t, Node *s) {
  if (s) t->sz+= s->sz, t->sum[0]+= s->sum[0], t->sum[1]+= s->sum[1], t->psum+= s->psum;
 }
 static inline void pushup(Node *t) {
  t->sz= 1, t->sum[0]= t->dat[0], t->sum[1]= t->dat[1], t->psum= (i128)(t->dat[0]) * t->dat[1];
  if (t->flg) t->sz= -t->sz, t->sum[0]= -t->sum[0], t->sum[1]= -t->sum[1], t->psum= -t->psum;
  add_(t, t->ch[0]), add_(t, t->ch[1]);
 }
 static inline int dir(Node *&t) {
  if (t->par) {
   if (t->par->ch[0] == t) return 0;
   if (t->par->ch[1] == t) return 1;
  }
  return 2;
 }
 static inline void rot(Node *t) {
  Node *p= t->par;
  int d= dir(t);
  if ((p->ch[d]= t->ch[!d])) p->ch[d]->par= p;
  t->ch[!d]= p, pushup(p), pushup(t);
  if (t->par= p->par; (d= dir(p)) < 2) p->par->ch[d]= t, pushup(t->par);
  p->par= t;
 }
 static inline Node *splay(Node *t) {
  eval(t);
  for (int t_d= dir(t), p_d; t_d < 2; rot(t), t_d= dir(t)) {
   if ((p_d= dir(t->par)) < 2) eval(t->par->par);
   if (eval(t->par), eval(t); p_d < 2) rot(t_d == p_d ? t->par : t);
  }
  return t;
 }
 static inline void bin_search(Node *t, i64 k, bool b, Node *ret[2]) {
  while (t) {
   eval(t);
   i64 tmp= t->dat[b];
   bool c;
   if (tmp == k) {
    c= t->flg ^ b ^ 1;
   } else {
    c= tmp < k;
   }
   ret[!c]= t;
   t= t->ch[c];
  }
 }
 inline void fix_fmin() {
  Node *fmin_pos[2], *e0_pos[2];
  bin_search(root, 0, !conj, fmin_pos);
  bin_search(root, 0, conj, e0_pos);
  if (e0_pos[0] == fmin_pos[0]) {
   fmin= e0;
   return;
  }
  if (e0_pos[1]->dat[conj] <= fmin_pos[0]->dat[conj]) {
   root= splay(e0_pos[0]);
   Node *tmp= e0_pos[0]->ch[1];
   tmp->par= nullptr;
   splay(fmin_pos[1]);
   fmin= fmin_pos[1]->ch[0]->psum;
   fmin_pos[1]->par= e0_pos[0], e0_pos[0]->ch[1]= fmin_pos[1];
  } else {
   root= splay(e0_pos[1]);
   Node *tmp= e0_pos[1]->ch[0];
   tmp->par= nullptr;
   splay(fmin_pos[0]);
   fmin= -fmin_pos[0]->ch[1]->psum;
   fmin_pos[0]->par= e0_pos[1], e0_pos[1]->ch[0]= fmin_pos[0];
  }
  if (conj) fmin= -fmin;
  fmin+= e0;
 }
 inline void fix_e0() {
  Node *fmin_pos[2], *e0_pos[2];
  bin_search(root, 0, !conj, fmin_pos);
  bin_search(root, 0, conj, e0_pos);
  if (e0_pos[0] == fmin_pos[0]) {
   e0= fmin;
   return;
  }
  if (e0_pos[1]->dat[conj] <= fmin_pos[0]->dat[conj]) {
   root= splay(e0_pos[0]);
   Node *tmp= e0_pos[0]->ch[1];
   tmp->par= nullptr;
   splay(fmin_pos[1]);
   e0= -fmin_pos[1]->ch[0]->psum;
   fmin_pos[1]->par= e0_pos[0], e0_pos[0]->ch[1]= fmin_pos[1];
  } else {
   root= splay(e0_pos[1]);
   Node *tmp= e0_pos[1]->ch[0];
   tmp->par= nullptr;
   splay(fmin_pos[0]);
   e0= fmin_pos[0]->ch[1]->psum;
   fmin_pos[0]->par= e0_pos[1], e0_pos[1]->ch[0]= fmin_pos[0];
  }
  if (conj) e0= -e0;
  e0+= fmin;
 }
 static void dump(Node *t, std::vector<Node *> &vec) {
  if (!t) return;
  eval(t);
  dump(t->ch[0], vec);
  vec.emplace_back(t);
  dump(t->ch[1], vec);
 }
 Node *root, *inf, *minf;
 i128 e0, fmin;
 bool conj;
public:
 std::vector<Node *> dump() {
  std::vector<Node *> vec;
  dump(root, vec);
  return vec;
 }
 PiecewiseLinearConvexfunction(): e0(0), fmin(0), conj(false) {
  Node *tmp= new Node;
  root= new Node, inf= new Node, minf= new Node;
  tmp->dat[0]= inf->dat[0]= inf->dat[1]= INF * 2;
  root->dat[0]= minf->dat[0]= minf->dat[1]= -INF * 2;
  root->ch[0]= minf, minf->par= root;
  tmp->ch[1]= inf, inf->par= tmp;
  root->ch[1]= tmp, tmp->par= root;
  minf->flg= 0, root->flg= 1, tmp->flg= 0, inf->flg= 1;
 }
 void conjugation() {
  conj= !conj;
  std::swap(e0, fmin);
  e0= -e0, fmin= -fmin;
 }
 void add_const(i128 c) { e0+= c, fmin+= c; }
 // + a|x-c|
 void add_abs_a_xc(i64 a, i64 c) { add_ax_bx(-a, a, c); }
 // f(x) + / a(x-c) (x<c )
 // ._._._.\ b(x-c) (x>=c)
 void add_ax_bx(i64 a, i64 b, i64 c) {
  e0+= 0 < c ? i128(a) * (-c) : i128(b) * (-c);
  Node *pos[2]= {nullptr, nullptr};
  bin_search(root, c, conj, pos);
  Node *ll= splay(pos[0]), *rr= ll->ch[1];
  ll->ch[1]= rr->par= nullptr;
  if (pos[0]->dat[conj] < c) {
   Node *l= new Node, *r= new Node;
   l->dat[!conj]= r->dat[!conj]= pos[0]->dat[!conj];
   l->dat[conj]= r->dat[conj]= c;
   l->flg= conj, r->flg= !conj;
   l->ch[0]= ll, ll->par= l;
   r->ch[1]= rr, rr->par= r;
   ll= l, rr= r;
  }
  i64 aa[2]= {0, 0};
  aa[!conj]= a, propagate(ll, aa);
  aa[!conj]= b, propagate(rr, aa);
  eval(ll);
  ll->ch[1]= rr, rr->par= ll;
  root= ll;
  fix_fmin();
 }
 // min_{y∈[a,b]}{f(x-y) + cy}
 void convex_conv_range_linear(i64 a, i64 b, i64 c) { conjugation(), add_ax_bx(a, b, c), conjugation(); }
 // min_{y∈[x-b,x-a]}{f(y)}
 void chmin(i64 a, i64 b) { convex_conv_range_linear(a, b, 0); }
 // min_{y<=x}f(y)
 void cumulate_min_l_to_r() {
  Node *fmin_pos[2];
  bin_search(root, 0, !conj, fmin_pos);
  root= splay(fmin_pos[1]);
  inf->ch[0]= inf->ch[1]= nullptr;
  if (root->dat[!conj] > 0) {
   Node *tmp= new Node;
   tmp->dat[conj]= INF * 2;
   root->dat[!conj]= tmp->dat[!conj]= 0;
   tmp->ch[1]= inf, inf->par= tmp;
   root->ch[1]= tmp, tmp->par= root;
   fmin_pos[0]= root, fmin_pos[1]= tmp;
  } else {
   root->dat[conj]= INF * 2;
   root->ch[1]= inf, inf->par= root;
  }
  if (fmin_pos[0]->dat[conj] <= 0) e0= fmin;
 }
 // f(x-a)
 void shift(i64 a) {
  i64 aa[2]= {0, 0};
  aa[conj]= a, propagate(root, aa);
  fix_e0();
 }
 i128 eval0() const { return e0; }
 i128 min() const { return fmin; }
 std::array<i64, 2> argmin() {
  Node *fmin_pos[2];
  bin_search(root, 0, !conj, fmin_pos);
  return {fmin_pos[0]->dat[conj], fmin_pos[1]->dat[conj]};
 }
};
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_a_xc(1, a);
   f.add_const(b);
  } else cout << f.argmin()[0] << " " << f.min() << '\n';
 }
 return 0;
}
}
// https://atcoder.jp/contests/dwango2016-prelims/tasks/dwango2016qual_e
namespace atcoder_dwango2016qual_e {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, L;
 cin >> N >> L;
 PiecewiseLinearConvexfunction f;
 for (int prev= -1, t, P; N--; prev= t) {
  cin >> t >> P;
  if (prev != t) f.cumulate_min_l_to_r();
  f.add_abs_a_xc(1, P);
 }
 cout << 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.conjugation();
 for (int i= 0; i < N; ++i) {
  f.cumulate_min_l_to_r();
  f.shift(B[i] - A[i]);
  f.add_abs_a_xc(1, 0);
 }
 cout << f.eval0() << '\n';
 return 0;
}
}
// https://atcoder.jp/contests/arc123/tasks/arc123_d
namespace ARC123D {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 PiecewiseLinearConvexfunction f;
 long long pA;
 for (int i= 0; i < N; ++i) {
  long long A;
  cin >> A;
  if (i) f.shift(max(A - pA, 0ll)), f.cumulate_min_l_to_r();
  f.add_abs_a_xc(1, 0), f.add_abs_a_xc(1, A);
  pA= A;
 }
 cout << f.min() << '\n';
 return 0;
}
}
// https://atcoder.jp/contests/arc070/tasks/arc070_c
namespace ARC070E {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N;
 cin >> N;
 PiecewiseLinearConvexfunction f;
 long long pw;
 for (int i= 0; i < N; ++i) {
  long long l, r;
  cin >> l >> r;
  long long w= r - l;
  if (i) f.chmin(-w, pw);
  f.add_abs_a_xc(1, l);
  pw= w;
 }
 cout << f.min() << '\n';
 return 0;
}
}
// https://yukicoder.me/problems/no/1467
namespace yukicoder1467 {
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 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) {
  PiecewiseLinearConvexfunction f;
  f.conjugation();
  for (int i= 0; i < n; ++i) {
   f.shift(a[i] - b[i] * k);
   f.cumulate_min_l_to_r();
   if (i < n - 1) f.add_abs_a_xc(vec[i + 1] - vec[i], 0);
   else f.conjugation(), f.cumulate_min_l_to_r(), f.conjugation();
  }
  cout << f.min() << '\n';
 }
 return 0;
}
}
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 // ABC127F::main();
 // atcoder_dwango2016qual_e::main();
 // atcoder_kupc2016_h::main();
 // ARC123D::main();
 // ARC070E::main();
 yukicoder1467::main();
 return 0;
}