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

提出ソース

結果

問題	No.1467 Selling Cars
ユーザー	hashiryo
提出日時	2023-02-20 19:25:50
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,180 ms / 4,000 ms
コード長	10,929 bytes
コンパイル時間	2,583 ms
コンパイル使用メモリ	217,412 KB
実行使用メモリ	503,292 KB
最終ジャッジ日時	2023-09-28 15:49:47
合計ジャッジ時間	27,394 ms
ジャッジサーバーID （参考情報）	judge12 / judge11

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,170 ms 502,440 KB
testcase_01	AC	997 ms 502,692 KB
testcase_02	AC	2 ms 4,376 KB
testcase_03	AC	1,000 ms 503,204 KB
testcase_04	AC	1,003 ms 503,152 KB
testcase_05	AC	997 ms 503,292 KB
testcase_06	AC	1,008 ms 503,180 KB
testcase_07	AC	995 ms 503,136 KB
testcase_08	AC	1,003 ms 503,256 KB
testcase_09	AC	3 ms 4,376 KB
testcase_10	AC	2 ms 4,380 KB
testcase_11	AC	652 ms 326,632 KB
testcase_12	AC	790 ms 401,336 KB
testcase_13	AC	744 ms 370,512 KB
testcase_14	AC	104 ms 55,780 KB
testcase_15	AC	223 ms 122,184 KB
testcase_16	AC	215 ms 111,488 KB
testcase_17	AC	603 ms 301,484 KB
testcase_18	AC	733 ms 371,340 KB
testcase_19	AC	1,124 ms 439,700 KB
testcase_20	AC	1,155 ms 491,764 KB
testcase_21	AC	1,091 ms 499,828 KB
testcase_22	AC	1,180 ms 464,072 KB
testcase_23	AC	1,139 ms 480,792 KB
testcase_24	AC	1,132 ms 497,500 KB
testcase_25	AC	35 ms 20,628 KB
testcase_26	AC	405 ms 192,884 KB
testcase_27	AC	392 ms 192,640 KB
testcase_28	AC	588 ms 238,716 KB
testcase_29	AC	124 ms 63,364 KB
testcase_30	AC	143 ms 75,356 KB
testcase_31	AC	2 ms 4,380 KB
testcase_32	AC	2 ms 4,376 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(); };
}
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};
 };
 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]) << ") }";
 }
 // 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) t->dat[0]+= x[0], t->laz[0]+= x[0], t->dat[1]+= x[1], t->laz[1]+= x[1];
 }
 static inline void push(Node *t) { propagate(t->ch[0], t->laz), propagate(t->ch[1], t->laz), t->laz[0]= t->laz[1]= 0; }
 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, t->par= p->par;
  if ((d= dir(p)) < 2) p->par->ch[d]= t;
  p->par= t;
 }
 static inline void splay(Node *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) rot(t_d == p_d ? t->par : t);
 }
 static inline void bin_search(Node *&t, i64 k, bool b) {
  for (Node *s;; t= s) {
   push(t);
   i64 tmp= t->dat[b];
   if (tmp == k) break;
   if (s= t->ch[tmp < k]; !s) break;
  }
  splay(t);
 }
 static inline i128 eval(Node *t, i64 x, i64 &p) {
  if (!t) return 0;
  push(t);
  i128 ret= eval(t->ch[0], x, p);
  if (i64 tmp= x - t->dat[0]; tmp > 0) {
   ret+= i128(tmp) * (t->dat[1] - p);
   p= t->dat[1];
   ret+= eval(t->ch[1], x, p);
  }
  return ret;
 }
 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 A;
 i128 C;
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(): A(0), C(0) { root= new Node, root->dat[0]= -INF * 2, root->dat[1]= 0; }
 // f(x) := 0 if x == 0 else ∞
 PiecewiseLinearConvexfunction(int a): A(-INF * 2), C(0) { root= new Node, root->dat[0]= 0, root->dat[1]= INF * 2; }
 // f(x) + c
 void add_const(i64 c) { C+= c; }
 // f(x) + ax+c
 void add_linear(i64 a, i64 c= 0) {
  A+= a, C+= c;
  i64 aa[2]= {0, a};
  propagate(root, aa);
 }
 // f(x-a)
 void shift(i64 a) {
  C-= i128(A) * a;
  i64 aa[2]= {a, 0};
  propagate(root, aa);
 }
 // f(x) + a * max{x, 0}
 void add_relu(i64 a) {
  i64 aa[2]= {0, a};
  bin_search(root, 0, 0);
  if (i64 tmp= root->dat[0]; tmp) {
   if (tmp > 0 && !root->ch[0]) {
    Node *t= new Node;
    t->dat[1]= A;
    t->ch[1]= root, root->par= t;
    root= t;
   } else {
    if (tmp > 0) {
     Node *s= root->ch[0];
     for (;; s= s->ch[1])
      if (push(s); !s->ch[1]) break;
     splay(s), root= s;
    }
    Node *t= new Node;
    t->dat[1]= root->dat[1];
    t->ch[1]= root->ch[1];
    if (t->ch[1]) t->ch[1]->par= t;
    root->ch[1]= nullptr;
    t->ch[0]= root, root->par= t;
    root= t;
   }
  }
  Node *l= root->ch[0];
  root->ch[0]= nullptr;
  propagate(root, aa);
  push(root), root->ch[0]= l;
 }
 // min_{y∈[0,a]}{f(x-y)}
 void chmin_sliding_window(i64 a) {
  i64 aa[2]= {a, 0};
  bin_search(root, 0, 1);
  if (i64 tmp= root->dat[1]; tmp) {
   if (tmp > 0 && !root->ch[0]) {
    Node *t= new Node;
    t->dat[0]= -INF;
    t->ch[1]= root, root->par= t;
    root= t;
   } else {
    if (tmp > 0) {
     Node *s= root->ch[0];
     for (;; s= s->ch[1])
      if (push(s); !s->ch[1]) break;
     splay(s), root= s;
    }
    Node *t= new Node;
    t->dat[0]= root->dat[0];
    t->ch[1]= root->ch[1];
    if (t->ch[1]) t->ch[1]->par= t;
    root->ch[1]= nullptr;
    t->ch[0]= root, root->par= t;
    root= t;
   }
  }
  Node *l= root->ch[0];
  root->ch[0]= nullptr;
  propagate(root, aa);
  push(root), root->ch[0]= l;
 }
 // min_{y<=x} f(y)
 void cumulative_chmin() {
  bin_search(root, 0, 1);
  if (i64 tmp= root->dat[1]; tmp < 0) {
   Node *t= root->ch[1];
   for (;; t= t->ch[0])
    if (push(t); !t->ch[0]) break;
   splay(t), root= t;
  }
  root->ch[1]= nullptr, root->dat[1]= 0;
 }
 // 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); }
 // f(x)
 i128 eval(i64 x) {
  i64 p= A;
  return eval(root, x, p) + i128(A) * x + C;
 }
 std::array<i64, 2> argmin() {
  std::array<i64, 2> ret;
  bin_search(root, 0, 1);
  if (i64 tmp= root->dat[1]; tmp <= 0) {
   Node *t= root->ch[1];
   for (;; t= t->ch[0])
    if (push(t); !t->ch[0]) break;
   if (tmp) ret= {t->dat[0], t->dat[0]};
   else ret= {root->dat[0], t->dat[0]};
   splay(t), root= t;
  } else if (tmp > 0) ret= {root->dat[0], root->dat[0]};
  return ret;
 }
 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();
 }
 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;
}