結果

問題 No.1467 Selling Cars
ユーザー hashiryohashiryo
提出日時 2023-02-22 16:37:06
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 10,216 bytes
コンパイル時間 2,524 ms
コンパイル使用メモリ 216,504 KB
実行使用メモリ 752,992 KB
最終ジャッジ日時 2023-09-30 00:14:51
合計ジャッジ時間 30,638 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 AC 567 ms
377,048 KB
testcase_02 AC 1 ms
4,380 KB
testcase_03 MLE -
testcase_04 MLE -
testcase_05 MLE -
testcase_06 MLE -
testcase_07 MLE -
testcase_08 MLE -
testcase_09 AC 3 ms
4,380 KB
testcase_10 AC 2 ms
4,376 KB
testcase_11 AC 771 ms
487,976 KB
testcase_12 MLE -
testcase_13 MLE -
testcase_14 AC 119 ms
81,808 KB
testcase_15 AC 259 ms
181,468 KB
testcase_16 AC 251 ms
165,100 KB
testcase_17 AC 699 ms
450,332 KB
testcase_18 MLE -
testcase_19 MLE -
testcase_20 MLE -
testcase_21 MLE -
testcase_22 MLE -
testcase_23 MLE -
testcase_24 MLE -
testcase_25 AC 40 ms
29,420 KB
testcase_26 AC 469 ms
287,588 KB
testcase_27 AC 458 ms
287,176 KB
testcase_28 AC 668 ms
356,476 KB
testcase_29 AC 140 ms
93,364 KB
testcase_30 AC 166 ms
111,384 KB
testcase_31 AC 2 ms
4,376 KB
testcase_32 AC 1 ms
4,380 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 dx= 0, slope= 0, laz= 0, x= 0;
  i128 y= 0;
 };
 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 void propagate(Node *t, i64 a) {
  if (t) t->slope+= a, t->laz+= a, t->y+= i128(a) * t->x;
 }
 static inline void push(Node *t) {
  if (t->laz) propagate(t->ch[0], t->laz), propagate(t->ch[1], t->laz), t->laz= 0;
 }
 static inline void pushup(Node *t) {
  t->x= t->dx, t->y= i128(t->slope) * t->dx;
  if (t->ch[0]) t->x+= t->ch[0]->x, t->y+= t->ch[0]->y;
  if (t->ch[1]) t->x+= t->ch[1]->x, t->y+= t->ch[1]->y;
 }
 static inline int dir(Node *t) { return t->par->ch[1] == t; }
 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, t->par= p->par;
  if (p->par) p->par->ch[dir(p)]= t;
  p->par= t;
 }
 static inline void splay(Node *t) {
  for (Node *p= t->par; p; p= t->par) {
   if (Node *pp= p->par; pp) rot(dir(t) == dir(p) ? p : t), rot(t), pushup(pp), pushup(p);
   else rot(t), pushup(p);
  }
  pushup(t);
 }
 static inline void slope_search(Node *&t, i64 k) {
  for (Node *s;; t= s) {
   push(t);
   i64 tmp= t->slope;
   if (tmp == k) break;
   if (s= t->ch[tmp < k]; !s) break;
  }
  splay(t);
 }
 static inline void x_search(Node *&t, i64 x) {
  for (bool c;; t= t->ch[c]) {
   push(t);
   i64 l= t->ch[0] ? t->ch[0]->x : 0, r= l + t->dx;
   if (l <= x && x <= r) return splay(t);
   if ((c= (r < x))) x-= r;
  }
 }
 static void dump(Node *t, std::vector<Node *> &vec) {
  if (!t) return;
  push(t);
  dump(t->ch[0], vec);
  vec.emplace_back(t);
  dump(t->ch[1], vec);
 }
 static int size(Node *t) {
  if (!t) return 0;
  return size(t->ch[0]) + size(t->ch[1]) + 1;
 }
 static int depth(Node *t) {
  if (!t) return 0;
  return std::max(depth(t->ch[0]), depth(t->ch[1])) + 1;
 }
 static inline void debugoutput(Node *t, int d) {
  if (!t) return;
  push(t);
  debugoutput(t->ch[0], d + 1);
  for (int i= 0; i < d; ++i) std::cerr << "   ";
  std::cerr << "■ " << t << '\n';
  debugoutput(t->ch[1], d + 1);
 }
 Node *root;
 i64 lb;
 i128 lby;
public:
 std::vector<Node *> dump() {
  std::vector<Node *> vec;
  dump(root, vec);
  return vec;
 }
 int depth() { return depth(root); }
 int size() { return size(root); }
 void debugoutput() { debugoutput(root, 0); }
 // f(x) := 0
 PiecewiseLinearConvexfunction(): lb(-INF * 2), lby(0) { root= new Node, root->x= root->dx= INF * 4; }
 // f(x) := 0 if x == 0 else ∞
 PiecewiseLinearConvexfunction(int a): lb(0), lby(0) { root= new Node; }
 // 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 + root->x <= 0) return;
  x_search(root, -lb);
  i64 l= root->ch[0] ? root->ch[0]->x : 0, r= l + root->dx;
  if (l == -lb) {
   Node *t= root->ch[0];
   root->ch[0]= nullptr;
   propagate(root, a);
   push(root);
   root->ch[0]= t;
  } else if (r == -lb) {
   propagate(root->ch[1], a);
  } else {
   Node *t= new Node;
   t->slope= root->slope;
   t->dx= r + lb;
   t->ch[1]= root->ch[1];
   if (t->ch[1]) t->ch[1]->par= t;
   pushup(t), propagate(t, a);
   root->ch[1]= t, t->par= root;
   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 (root->slope < 0) {
   if (!root->ch[1]) root->ch[1]= new Node;
   Node *t= root->ch[1];
   t->x= t->dx= INF * 2, t->slope= 0, t->ch[0]= t->ch[1]= nullptr, t->y= 0, t->par= root;
  } else root->ch[1]= nullptr, root->dx= INF * 2, root->slope= 0, pushup(root);
 }
 i128 eval(i64 x) {
  if (x-= lb; x < 0 || root->x < x) return INF;
  x_search(root, x);
  if (root->ch[0]) return lby + root->ch[0]->y + i128(x - root->ch[0]->x) * root->slope;
  return lby + i128(x) * root->slope;
 }
 std::array<i64, 2> argmin() {
  slope_search(root, 0);
  i64 l= lb + (root->ch[0] ? root->ch[0]->x : 0), r= l + root->dx;
  if (root->slope == 0) return {l, r};
  return 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);
 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(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';
 }
 return 0;
}
}
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 // ABC127F::main();
 // atcoder_kupc2016_h::main();
 yukicoder1467::main();
 return 0;
}
0