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

提出ソース

結果

問題	No.1467 Selling Cars
ユーザー	hashiryo
提出日時	2024-08-02 14:28:59
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	MLE
実行時間	-
コード長	12,003 bytes
コンパイル時間	2,547 ms
コンパイル使用メモリ	215,340 KB
実行使用メモリ	627,968 KB
最終ジャッジ日時	2024-08-02 14:29:26
合計ジャッジ時間	26,145 ms
ジャッジサーバーID （参考情報）	judge1 / judge5

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	MLE	-
testcase_01	AC	485 ms 314,752 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	MLE	-
testcase_04	MLE	-
testcase_05	MLE	-
testcase_06	MLE	-
testcase_07	MLE	-
testcase_08	MLE	-
testcase_09	AC	2 ms 6,940 KB
testcase_10	AC	3 ms 6,940 KB
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	AC	105 ms 68,736 KB
testcase_15	AC	228 ms 151,680 KB
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	MLE	-
testcase_20	MLE	-
testcase_21	MLE	-
testcase_22	MLE	-
testcase_23	MLE	-
testcase_24	MLE	-
testcase_25	AC	35 ms 24,960 KB
testcase_26	AC	376 ms 240,256 KB
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	AC	138 ms 93,312 KB
testcase_31	AC	2 ms 6,940 KB
testcase_32	AC	1 ms 6,940 KB

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

ソースコード

raw source code

// #define _GLIBCXX_DEBUG
#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 &u){if(!u)os<<"0";__int128_t tmp=u<0?(os<<"-",-u):u;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 &u){if(!u)os<<"0";__uint128_t tmp=u;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(...) (void(0))
#define debugArray(x,n) (void(0))
#define debugMatrix(x,h,w) (void(0))
// 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(); };
}
// clang-format off
template<class T>struct make_long{using type= T;};
template<>struct make_long<int8_t>{using type= int16_t;};
template<>struct make_long<uint8_t>{using type= uint16_t;};
template<>struct make_long<int16_t>{using type= int32_t;};
template<>struct make_long<uint16_t>{using type= uint32_t;};
template<>struct make_long<int32_t>{using type= int64_t;};
template<>struct make_long<uint32_t>{using type= uint64_t;};
template<>struct make_long<int64_t>{using type= __int128_t;};
template<>struct make_long<uint64_t>{using type= __uint128_t;};
template<>struct make_long<float>{using type= double;};
template<>struct make_long<double>{using type= long double;};
template<class T> using make_long_t= typename make_long<T>::type;
// clang-format on
template <class T> class PiecewiseLinearConvex {
 using D= make_long_t<T>;
 struct Node {
  Node *ch[2], *par;
  T z, x, d, a;
  D s;
  size_t sz;
  friend std::ostream &operator<<(std::ostream &os, const Node &t) { return os << "{z:" << t.z << ",x:" << t.x << ",d:" << t.d << ",a:" << t.a << ",s:" << t.s << ",sz:" << t.sz << ",ch:(" << t.ch[0] << "," << t.ch[1] << "),par:" << t.par << "}"; }
 };
 using np= Node *;
 static inline void info(np t, int d, std::stringstream &ss) {
  if (!t) return;
  push(t), info(t->ch[0], d + 1, ss);
  for (int i= 0; i < d; ++i) ss << "   ";
  ss << " ■ " << *t << '\n', info(t->ch[1], d + 1, ss);
 }
 static inline void dump_xs(np t, std::vector<T> &xs) {
  if (t) push(t), dump_xs(t->ch[0], xs), xs.push_back(t->x), dump_xs(t->ch[1], xs);
 }
 static inline void dump_slopes_l(np t, T ofs, std::vector<T> &as) {
  if (t) push(t), dump_slopes_l(t->ch[1], ofs, as), ofs+= sl(t->ch[1]) + t->d, as.push_back(-ofs), dump_slopes_l(t->ch[0], ofs, as);
 }
 static inline void dump_slopes_r(np t, T ofs, std::vector<T> &as) {
  if (t) push(t), dump_slopes_r(t->ch[0], ofs, as), ofs+= sl(t->ch[0]) + t->d, as.push_back(ofs), dump_slopes_r(t->ch[1], ofs, as);
 }
 static inline void update(np t) {
  t->sz= 1, t->a= t->d, t->s= D(t->x) * t->d;
  if (np l= t->ch[0]; l) t->sz+= l->sz, t->a+= l->a, t->s+= l->s;
  if (np r= t->ch[1]; r) t->sz+= r->sz, t->a+= r->a, t->s+= r->s;
 }
 static inline void prop(np t, T v) { t->z+= v, t->s+= D(v) * t->a, t->x+= v; }
 static inline void push(np t) {
  if (t->z != 0) {
   if (t->ch[0]) prop(t->ch[0], t->z);
   if (t->ch[1]) prop(t->ch[1], t->z);
   t->z= 0;
  }
 }
 static inline void rot(np t) {
  np p= t->par;
  if (bool d= p->ch[1] == t; (p->ch[d]= std::exchange(t->ch[!d], p))) p->ch[d]->par= p;
  if ((t->par= std::exchange(p->par, t))) t->par->ch[t->par->ch[1] == p]= t;
  update(p);
 }
 static inline void splay(np t) {
  for (np p= t->par; p; rot(t), p= t->par)
   if (p->par) rot(p->par->ch[p->ch[1] == t] == p ? p : t);
 }
 static inline T sl(np t) { return t ? t->a : 0; }
 static inline D sum(np t) { return t ? t->s : 0; }
 template <bool r> static inline bool lt(T a, T b) {
  if constexpr (r) return b < a;
  else return a < b;
 }
 template <bool r> inline D calc_y(np t, T x, T ol, T ou) {
  if (t) {
   for (np n;; t= n) {
    if (push(t); lt<r>(t->x, x)) n= t->ch[!r];
    else {
     ol+= sl(t->ch[!r]), ou+= sum(t->ch[!r]);
     if (t->x == x) break;
     ol+= t->d, ou+= D(t->x) * t->d, n= t->ch[r];
    }
    if (!n) break;
   }
   splay(t), splay(mn);
  }
  if constexpr (r) return D(x) * ol - ou;
  else return ou - D(x) * ol;
 }
 np mn;
 bool bf[2];
 T o[2], rem, bx[2];
 D y;
 D calc_y(T x) {
  if (!mn) return 0;
  if (mn->x == x) return 0;
  return x < mn->x ? calc_y<0>(mn->ch[0], x, o[0], D(mn->x) * o[0]) : calc_y<1>(mn->ch[1], x, o[1], D(mn->x) * o[1]);
 }
 template <bool r> void slope_lr() {
  np t= mn;
  if (!t) return;
  T ol= o[r];
  if constexpr (r) y-= sum(t->ch[r]) + D(t->x) * ol, rem+= ol + sl(t->ch[r]);
  else y+= sum(t->ch[r]) + D(t->x) * ol, rem-= ol + sl(t->ch[r]);
  for (; push(t), t->ch[r];) t= t->ch[r];
  splay(mn= t), o[r]= 0, o[!r]= t->d;
 }
 void slope_eval() {
  if (rem == 0 || !mn) return;
  bool neg= rem < 0;
  T p= neg ? -rem : rem, ol= 0;
  D ou= 0;
  np t= mn;
  if (ol= o[neg]; p <= ol) {
   o[neg]-= p, o[!neg]+= p, y+= D(t->x) * rem, rem= 0;
   return;
  }
  if (ou+= D(t->x) * ol, t= t->ch[neg]; ol + sl(t) < p) return neg ? slope_lr<1>() : slope_lr<0>();
  for (T s, l;;) {
   if (push(t), s= ol + sl(t->ch[!neg]), l= s + t->d; p < s) t= t->ch[!neg];
   else if (l < p) ol= l, ou+= sum(t->ch[!neg]) + D(t->x) * t->d, t= t->ch[neg];
   else {
    if (o[neg]= l - p, o[!neg]= p - s; neg) y+= D(t->x) * s - (ou + sum(t->ch[!neg]));
    else y-= D(t->x) * s - (ou + sum(t->ch[!neg]));
    break;
   }
  }
  splay(mn= t), y+= D(t->x) * rem, rem= 0;
 }
 template <bool r> void add_inf(T x0) {
  if (bf[r] && !lt<r>(bx[r], x0)) return;
  if (assert(!bf[!r] || !lt<r>(bx[!r], x0)), bf[r]= true, bx[r]= x0; !mn) return;
  if (slope_lr<!r>(); !lt<r>(x0, mn->x)) return mn= nullptr, void();
  np t= mn, s= t;
  for (; t;)
   if (push(t); lt<r>(x0, t->x)) s= t, t= t->ch[r];
   else t= t->ch[!r];
  splay(s), s->ch[r]= nullptr, splay(mn);
 }
 void add_r(np t) {
  if (t) push(t), add_r(t->ch[0]), add_max(0, t->d, t->x), add_r(t->ch[1]);
 }
 void add_l(np t) {
  if (t) push(t), add_l(t->ch[0]), add_max(-t->d, 0, t->x), add_l(t->ch[1]);
 }
public:
 PiecewiseLinearConvex(): mn(nullptr), bf{0, 0}, rem(0), y(0) {}
 std::string info() {
  std::stringstream ss;
  if (ss << "\n rem:" << rem << ", y:" << y << ", mn:" << mn << "\n bf[0]:" << bf[0] << ", bf[1]:" << bf[1] << ", bx[0]:" << bx[0] << ", bx[1]:" << bx[1] << "\n " << "o[0]:" << o[0] << ", o[1]:" << o[1] << "\n"; mn) info(mn, 0, ss);
  return ss.str();
 }
 std::vector<T> dump_xs() {
  std::vector<T> xs;
  if (bf[0]) xs.push_back(bx[0]);
  if (mn) dump_xs(mn, xs);
  if (bf[1]) xs.push_back(bx[1]);
  return xs;
 }
 std::vector<std::pair<T, D>> dump_xys() {
  auto xs= dump_xs();
  std::vector<std::pair<T, D>> xys(xs.size());
  for (int i= xs.size(); i--;) xys[i]= {xs[i], operator()(xs[i])};
  return xys;
 }
 std::vector<T> dump_slopes() {
  std::vector<T> as;
  if (mn) as.push_back(-o[0]), dump_slopes_l(mn->ch[0], o[0], as), std::reverse(as.begin(), as.end()), as.push_back(o[1]), dump_slopes_r(mn->ch[1], o[1], as);
  else as.push_back(0);
  for (auto &a: as) a+= rem;
  return as;
 }
 // f(x) += c
 void add_const(D c) { y+= c; }
 // f(x) += ax, /
 void add_linear(T a) { rem+= a; }
 //  f(x) += max(a(x-x0),b(x-x0)), (a < b)
 void add_max(T a, T b, T x0) {
  assert(a < b);
  if (bf[0] && x0 <= bx[0]) y-= D(b) * x0, rem+= b;
  else if (bf[1] && bx[1] <= x0) y-= D(a) * x0, rem+= a;
  else if (mn) {
   np t= mn;
   for (;;) {
    if (push(t); t->x == x0) {
     t->d+= b - a;
     break;
    }
    np &n= t->ch[t->x < x0];
    if (!n) {
     n= new Node{{nullptr, nullptr}, t, 0, x0, b - a, b - a, D(x0) * (b - a), 1}, t= n;
     break;
    }
    t= n;
   }
   if (splay(t), splay(mn); x0 < mn->x) y-= D(b) * x0, rem+= b;
   else if (y-= D(a) * x0, rem+= a; x0 == mn->x) o[1]+= b - a;
  } else mn= new Node{{nullptr, nullptr}, nullptr, 0, x0, b - a, b - a, D(x0) * (b - a), 1}, y-= D(a) * x0, rem+= a, o[0]= 0, o[1]= b - a;
 }
 // f(x) +=  max(0, a(x-x0))
 void add_ramp(T a, T x0) {
  if (a != 0) a > 0 ? add_max(0, a, x0) : add_max(a, 0, x0);
 }
 // f(x) += a|x-x0|, \/
 void add_abs(T a, T x0) {
  if (assert(a >= 0); a != 0) add_max(-a, a, x0);
 }
 // right=false : f(x) +=  inf  (x < x_0), right=true: f(x) += inf  (x_0 < x)
 void add_inf(bool right= false, T x0= 0) { return right ? add_inf<1>(x0) : add_inf<0>(x0); }
 // f(x) <- f(x-x0)
 void shift(T x0) {
  if (bx[0]+= x0, bx[1]+= x0, y-= D(rem) * x0; mn) mn->z+= x0, mn->x+= x0;
 }
 // rev=false: f(x) <- min_{y<=x} f(y), rev=true : f(x) <- min_{x<=y} f(y)
 void chmin_cum(bool rev= false) {
  if (bf[0] && bf[1] && bx[0] == bx[1]) y+= D(rem) * bx[0], rem= 0;
  else if (slope_eval(); rem == 0) {
   if (mn) mn->d= o[rev], o[!rev]= 0, mn->ch[!rev]= nullptr;
  } else if ((rem > 0) ^ rev) assert(bf[rev]), y+= D(rem) * bx[rev], rem= 0, mn= nullptr;
  else if (bf[!rev]) {
   T p= std::abs(rem);
   np t= new Node{{nullptr, nullptr}, mn, 0, bx[!rev], p, p, D(bx[!rev]) * p, 1};
   if (mn) mn->ch[!rev]= t;
   mn= t, o[rev]= p, o[!rev]= 0;
  }
  bf[!rev]= false;
 }
 //  f(x) <- min_{lb<=y<=ub} f(x-y). (lb <= ub), \_/ -> \__/
 void chmin_slide_win(T lb, T ub) {
  assert(lb <= ub);
  if (bf[0] && bf[1] && bx[0] == bx[1]) y+= D(rem) * bx[0], rem= 0;
  else if (slope_eval(); rem == 0) {
   if (mn) {
    if (o[0] == 0) {
     if (mn->z+= ub, mn->x+= ub; mn->ch[0]) prop(mn->ch[0], lb - ub);
    } else if (o[1] == 0) {
     if (mn->z+= lb, mn->x+= lb; mn->ch[1]) prop(mn->ch[1], ub - lb);
    } else {
     np r= mn->ch[1], t= new Node{{nullptr, r}, mn, 0, mn->x, o[1], 0, 0, 1};
     if (update(t), prop(mn->ch[1]= t, ub - lb), mn->d= o[0], o[1]= 0, mn->z+= lb, mn->x+= lb; r) r->par= t;
    }
   }
  } else {
   bool r= rem > 0;
   T b[2]= {lb, ub};
   if (bf[!r]) {
    T p= r ? rem : -rem;
    np t= new Node{{nullptr, nullptr}, nullptr, 0, bx[!r], p, p, D(bx[!r]) * p, 1};
    if (mn) splay(mn), t->ch[r]= mn, mn->par= t;
    y+= D(rem) * bx[!r], rem= 0, mn= t, t->z+= b[r], t->x+= b[r], o[r]= p, o[!r]= 0;
   } else if (y-= D(rem) * b[r]; mn) splay(mn), mn->z+= b[r], mn->x+= b[r];
  }
  bx[0]+= lb, bx[1]+= ub;
 }
 D operator()(T x) { return assert(!bf[0] || bx[0] <= x), assert(!bf[1] || x <= bx[1]), calc_y(x) + D(rem) * x + y; }
 D min() { return slope_eval(), rem == 0 ? y : rem > 0 ? (assert(bf[0]), y + D(rem) * bx[0]) : (assert(bf[1]), y + D(rem) * bx[1]); }
 std::array<T, 2> argmin() {
  slope_eval();
  if (rem > 0) {
   assert(bf[0]);
   return {bx[0], bx[0]};
  }
  if (rem < 0) {
   assert(bf[1]);
   return {bx[1], bx[1]};
  }
  std::array<T, 2> ret= {bx[0], bx[1]};
  np t= mn;
  if (!t) return ret;
  bool r= o[0] == 0;
  if (!r && o[1] != 0) ret[0]= ret[1]= t->x;
  else if (ret[r]= t->x, t= t->ch[!r]; t) {
   for (; t->ch[r];) push(t), t= t->ch[r];
   splay(t), ret[!r]= t->x, splay(mn);
  } else assert(bf[!r]);
  return ret;
 }
 size_t size() { return mn ? mn->sz : 0; }
 PiecewiseLinearConvex &operator+=(const PiecewiseLinearConvex &r) {
  if (y+= r.y, rem+= r.rem; r.bf[0]) add_inf(false, r.bx[0]);
  if (r.bf[1]) add_inf(true, r.bx[1]);
  if (r.mn) add_l(r.mn->ch[0]), add_r(r.mn->ch[1]), add_max(-r.o[0], r.o[1], r.mn->x);
  return *this;
 }
};
using namespace std;
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) {
  PiecewiseLinearConvex<long long> f;
  f.add_inf();
  for (int i= 0; i < n; ++i) {
   f.chmin_cum();
   f.shift(a[i] - b[i] * k);
   if (i < n - 1) f.add_abs(vec[i + 1] - vec[i], 0);
  }
  cout << (long long)f(0) << '\n';
 }
 return 0;
}

yukicoder

結果

テストケース

ソースコード