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

提出ソース

結果

問題	No.1467 Selling Cars
ユーザー	hashiryo
提出日時	2023-02-22 22:58:42
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	976 ms / 4,000 ms
コード長	10,385 bytes
コンパイル時間	2,535 ms
コンパイル使用メモリ	217,688 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-07-22 23:17:53
合計ジャッジ時間	18,898 ms
ジャッジサーバーID （参考情報）	judge4 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	946 ms 6,812 KB
testcase_01	AC	294 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	668 ms 6,940 KB
testcase_04	AC	668 ms 6,940 KB
testcase_05	AC	676 ms 6,940 KB
testcase_06	AC	674 ms 6,944 KB
testcase_07	AC	699 ms 6,944 KB
testcase_08	AC	658 ms 6,944 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,940 KB
testcase_11	AC	426 ms 6,944 KB
testcase_12	AC	520 ms 6,940 KB
testcase_13	AC	492 ms 6,944 KB
testcase_14	AC	62 ms 6,940 KB
testcase_15	AC	130 ms 6,940 KB
testcase_16	AC	142 ms 6,940 KB
testcase_17	AC	391 ms 6,944 KB
testcase_18	AC	488 ms 6,940 KB
testcase_19	AC	902 ms 6,944 KB
testcase_20	AC	863 ms 6,940 KB
testcase_21	AC	779 ms 6,944 KB
testcase_22	AC	976 ms 6,944 KB
testcase_23	AC	877 ms 6,940 KB
testcase_24	AC	836 ms 6,940 KB
testcase_25	AC	23 ms 6,944 KB
testcase_26	AC	273 ms 6,940 KB
testcase_27	AC	263 ms 6,944 KB
testcase_28	AC	452 ms 6,944 KB
testcase_29	AC	80 ms 6,940 KB
testcase_30	AC	95 ms 6,940 KB
testcase_31	AC	2 ms 6,940 KB
testcase_32	AC	2 ms 6,940 KB

権限があれば一括ダウンロードができます

ソースコード

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(); };
}
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 << 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_id ch[2], par;
  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 void clear() { ni= 1; }
 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].x= ns[i].dx, ns[i].y= i128(ns[i].slope) * ns[i].dx;
  if (int j= ns[i].ch[0]; j) ns[i].x+= ns[j].x, ns[i].y+= ns[j].y;
  if (int j= ns[i].ch[1]; j) 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 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 lb;
 i128 lby;
public:
 void debugoutput() { debugoutput(root, 0); }
 // f(x) := 0
 PiecewiseLinearConvexfunction(): lb(-INF * 2), lby(0), root(ni++) { ns[root].x= ns[root].dx= INF * 4, ns[root].par= ns[root].ch[0]= ns[root].ch[1]= ns[root].slope= ns[root].laz= ns[root].y= 0; }
 // f(x) := 0 if x == 0 else ∞
 PiecewiseLinearConvexfunction(int a): lb(0), lby(0), root(ni++) { ns[root].x= ns[root].dx= ns[root].par= ns[root].ch[0]= ns[root].ch[1]= ns[root].slope= ns[root].laz= ns[root].y= 0; }
 // f(x) + c
 void add_const(i64 c) { lby+= c; }
 // f(x) + ax+c
 void add_linear(i64 a, i64 c= 0) { lby+= i128(a) * lb + c, propagate(root, a); }
 // f(x-a)
 void shift(i64 a) { lb+= a; }
 // f(x) + a * max{x, 0}
 void add_relu(i64 a) {
  if (0 <= lb) return add_linear(a);
  if (lb + ns[root].x <= 0) return;
  x_search(root, -lb);
  i64 l= ns[root].ch[0] ? ns[ns[root].ch[0]].x : 0, r= l + ns[root].dx;
  if (l == -lb) {
   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 == -lb) {
   propagate(ns[root].ch[1], a);
  } else {
   node_id i= ni++;
   ns[i].ch[0]= ns[i].laz= 0;
   ns[i].slope= ns[root].slope;
   ns[i].dx= r + lb;
   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= -lb - l, pushup(root);
  }
 }
 // f(x) + a * min{x,0} + b * max{x,0}
 void add_ax_bx(i64 a, i64 b) { add_linear(a), add_relu(b - a); }
 // f(x) + a * min{x-c,0} + b * max{x-c,0}
 void add_ax_bx_c(i64 a, i64 b, i64 c) { shift(-c), add_ax_bx(a, b), shift(c); }
 // f(x) + a * |x-c|
 void add_abs(i64 a, i64 c) { add_ax_bx_c(-a, a, c); }
 // min_{y<=x} f(y)
 void cumulative_chmin() {
  slope_search(root, 0);
  if (ns[root].slope < 0) {
   if (!ns[root].ch[1]) ns[root].ch[1]= ni++;
   node_id i= ns[root].ch[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);
 }
 i128 eval(i64 x) {
  if (x-= lb; x < 0 || ns[root].x < x) return INF;
  x_search(root, x);
  if (int i= ns[root].ch[0]; i) return lby + ns[i].y + i128(x - ns[i].x) * ns[root].slope;
  return lby + i128(x) * ns[root].slope;
 }
 std::array<i64, 2> argmin() {
  slope_search(root, 0);
  i64 l= lb + (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()[0]); }
};
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--) {
  // debug(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';
  }
  // f.debugoutput();
 }
 // f.debugoutput();
 // debug(f.lb);
 // debug(f.lby);
 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(1);
 for (int i= 0; i < N; ++i) {
  f.cumulative_chmin();
  f.shift(B[i] - A[i]);
  f.add_abs(1, 0);
 }
 cout << f.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(1);
  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();
 yukicoder1467::main();
 return 0;
}