test/yukicoder/2332.zalgo.test.cpp

• View this file on GitHub
• Last update: 2024-09-01 13:40:30+09:00
• Problem: https://yukicoder.me/problems/no/2332

Depends on

• 関数型や関数オブジェクトに関するテンプレート (src/Internal/function_traits.hpp)
• Li-Chao-Tree (src/Optimization/LiChaoTree.hpp)
• 最大最小を指定するための列挙型 (src/Optimization/MinMaxEnum.hpp)
• Z-Algorithm (src/String/z_algorithm.hpp)

Code

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/2332
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#include "src/String/z_algorithm.hpp"
#include "src/Optimization/LiChaoTree.hpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M;
 cin >> N >> M;
 vector<int> A(N), B(M), C(M);
 for (int i= 0; i < N; ++i) cin >> A[i];
 for (int i= 0; i < M; ++i) cin >> B[i];
 for (int i= 0; i < M; ++i) cin >> C[i];
 A.insert(A.end(), B.begin(), B.end());
 vector<int> Z= z_algorithm(A);
 Z= vector<int>(Z.begin() + N, Z.end());
 for (int &x: Z) x= min(x, N);
 auto f= [&](int x, long long a, long long b) { return a * x + b; };
 LiChaoTree lct(f, 0, 1e9 + 10);
 auto tree= lct.make_tree<MINIMIZE>();
 long long ans= 0;
 for (int i= 0; i < M; ++i) {
  if (ans >= 0) tree.insert(C[i], ans - (long long)C[i] * i, i + 1, i + Z[i] + 1);
  auto [a, b]= tree.query(i + 1);
  ans= b < 0 ? -1 : a;
 }
 cout << ans << '\n';
 return 0;
}

#line 1 "test/yukicoder/2332.zalgo.test.cpp"
// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/2332
// competitive-verifier: TLE 0.5
// competitive-verifier: MLE 64
#include <iostream>
#include <vector>
#line 3 "src/String/z_algorithm.hpp"
#include <algorithm>
#include <string>
#include <tuple>
template <class String> std::vector<int> z_algorithm(const String &s) {
 const int n= s.size();
 if (n == 0) return {};
 std::vector<int> z(n);
 for (int i= 1, j= 0; i < n; ++i) {
  int &k= z[i];
  for (k= (j + z[j] <= i) ? 0 : std::min(j + z[j] - i, z[i - j]); i + k < n && s[k] == s[i + k];) ++k;
  if (j + z[j] < i + z[i]) j= i;
 }
 return z[0]= n, z;
}
std::vector<int> z_to_kmp(const std::vector<int> &z) {
 const int n= z.size();
 std::vector<int> kmp(n + 1);
 kmp[0]= -1;
 for (int i= n; --i;) kmp[i + z[i]]= std::max(kmp[i + z[i]], z[i]);
 for (int i= n; i--;) kmp[i]= std::max(kmp[i], kmp[i + 1] - 1);
 return kmp;
}
namespace string_internal {
template <class String> auto run_enumerate_(const String &s, typename String::value_type a= 0) {
 using Run= std::tuple<int, int, int>;
 std::vector<Run> glb;
 auto rec= [&](auto rec, int l, int r) -> std::vector<Run> {
  if (r - l <= 1) return {};
  const int m= (l + r) / 2, lsz= m - l, rsz= r - m;
  std::vector<Run> run_l= lsz > 1 ? rec(rec, l, m) : std::vector<Run>(), run_r= rsz > 1 ? rec(rec, m, r) : std::vector<Run>();
  std::vector<typename String::value_type> rl(r - l + 1, a);
  std::copy(s.begin() + m, s.begin() + r, rl.begin()), std::copy(s.begin() + l, s.begin() + m, rl.begin() + rsz + 1);
  std::vector<int> zrl= z_algorithm(rl);
  std::reverse(rl.begin(), rl.end());
  std::vector<int> zrl_r= z_algorithm(rl);
  const int sz= rl.size();
  std::vector<Run> ret;
  auto push= [&](int b, int e, int p) { (b == l || e == r ? ret : glb).emplace_back(b, e, p); };
  std::vector<Run> run_m(rsz / 2 + 1);
  for (auto [b, e, p]: run_r) {
   if (b != m) ret.emplace_back(b, e, p);
   else run_m[p]= Run{b, e, p};
  }
  for (auto [b, e, p]: run_l)
   if (e != m) ret.emplace_back(b, e, p);
   else if (zrl[sz - p] == p) {
    if (std::get<2>(run_m[p])) push(b, std::get<1>(run_m[p]), p), run_m[p]= Run{};
    else push(b, m + p + zrl[p], p);
   } else push(b, m + zrl[sz - p], p);
  for (auto [b, e, p]: run_m)
   if (p) {
    if (zrl[sz - p] != p) push(m - zrl_r[sz - p], e, p);
    else if (2 * p > lsz || zrl[sz - 2 * p] < p) push(m - p - zrl_r[p], e, p);
   }
  for (int p= 1; p <= lsz; ++p)
   if (bool skpr= 2 * p <= rsz && zrl[p] >= p, skpl= 2 * p <= lsz && zrl[sz - 2 * p] >= p; zrl[sz - p] == p) {
    if (!skpl && !skpr) push(m - p - zrl_r[p], m + p + zrl[p], p);
   } else {
    if (!skpr)
     if (int b= m - zrl_r[sz - p], e= m + p + zrl[p]; e - b >= 2 * p) push(b, e, p);
    if (!skpl)
     if (int b= m - p - zrl_r[p], e= m + zrl[sz - p]; e - b >= 2 * p) push(b, e, p);
   }
  return ret;
 };
 std::vector<std::tuple<int, int, int>> runs= rec(rec, 0, s.size());
 std::copy(glb.begin(), glb.end(), std::back_inserter(runs)), std::sort(runs.begin(), runs.end()), runs.erase(std::unique(runs.begin(), runs.end(), [](auto &r1, auto &r2) { return std::get<0>(r1) == std::get<0>(r2) && std::get<1>(r1) == std::get<1>(r2); }), runs.end());
 int rn= runs.size(), n= s.size();
 glb.resize(rn);
 std::vector<int> pt(n);
 for (auto [l, r, p]: runs) ++pt[p];
 for (int i= 1; i < n; ++i) pt[i]+= pt[i - 1];
 for (int i= rn; i--;) glb[--pt[std::get<2>(runs[i])]]= {std::get<2>(runs[i]), std::get<0>(runs[i]), std::get<1>(runs[i])};
 return glb;
}
template <class Int, typename= std::enable_if_t<std::is_integral_v<Int>>> auto run_enumerate(const std::vector<Int> &s) { return run_enumerate_(s, *std::max_element(s.begin(), s.end()) + 1); }
template <class String> auto run_enumerate(const String &s) {
 auto v= s;
 std::sort(v.begin(), v.end()), v.erase(std::unique(v.begin(), v.end()), v.end());
 std::vector<int> t(s.size());
 for (int i= s.size(); i--;) t[i]= std::lower_bound(v.begin(), v.end(), s[i]) - v.begin();
 return run_enumerate_(t, v.size() + 1);
}
auto run_enumerate(const std::string &s) { return run_enumerate_(s); }
}
using string_internal::run_enumerate;
#line 2 "src/Optimization/LiChaoTree.hpp"
#include <limits>
#line 6 "src/Optimization/LiChaoTree.hpp"
#include <cassert>
#line 2 "src/Internal/function_traits.hpp"
#include <type_traits>
// clang-format off
namespace function_template_internal{
template<class C>struct is_function_object{
 template<class U,int dummy=(&U::operator(),0)> static std::true_type check(U *);
 static std::false_type check(...);
 static C *m;
 static constexpr bool value= decltype(check(m))::value;
};
template<class F,bool,bool>struct function_type_impl{using type= void;};
template<class F>struct function_type_impl<F,true,false>{using type= F *;};
template<class F>struct function_type_impl<F,false,true>{using type= decltype(&F::operator());};
template<class F> using function_type_t= typename function_type_impl<F,std::is_function_v<F>,is_function_object<F>::value>::type;
template<class... Args>struct result_type_impl{using type= void;};
template<class R,class... Args>struct result_type_impl<R(*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)>{using type= R;};
template<class C,class R,class... Args>struct result_type_impl<R(C::*)(Args...)const>{using type= R;};
template<class F> using result_type_t= typename result_type_impl<function_type_t<F>>::type;
template<class... Args>struct argument_type_impl{using type= void;};
template<class R,class... Args>struct argument_type_impl<R(*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)>{using type= std::tuple<Args...>;};
template<class C,class R,class... Args>struct argument_type_impl<R(C::*)(Args...)const>{using type= std::tuple<Args...>;};
template<class F> using argument_type_t= typename argument_type_impl<function_type_t<F>>::type;
}
using function_template_internal::result_type_t,function_template_internal::argument_type_t;
// clang-format on
#line 2 "src/Optimization/MinMaxEnum.hpp"
enum MinMaxEnum { MAXIMIZE= -1, MINIMIZE= 1 };
#line 9 "src/Optimization/LiChaoTree.hpp"
template <class F, class T> class LiChaoTree {};
template <class F, class T, class... Prms> class LiChaoTree<F, std::tuple<T, Prms...>> {
 using R= result_type_t<F>;
 F f;
 const T LB, UB;
 std::vector<std::tuple<Prms...>> ps;
 template <MinMaxEnum sgn, bool persistent> class LiChaoTreeInterface {
  LiChaoTree *ins;
  struct Node {
   int id= -1;
   Node *ch[2]= {nullptr, nullptr};
  } *root;
  inline R eval(int id, T x) const { return std::apply(ins->f, std::tuple_cat(std::make_tuple(x), ins->ps[id])); }
  static inline bool cmp(const R &p, const R &n, int pi, int ni) {
   if constexpr (sgn == MINIMIZE) return p > n || (p == n && pi > ni);
   else return p < n || (p == n && pi > ni);
  }
  inline bool cmp(T x, int pi, int ni) const {
   if (ni == -1) return false;
   if (pi == -1) return true;
   return cmp(eval(pi, x), eval(ni, x), pi, ni);
  }
  static inline T ub(T r) {
   if constexpr (std::is_floating_point_v<T>) return r;
   else return r - 1;
  }
  inline void addl(Node *&t, int id, T xl, T xr) {
   if (!t) return t= new Node{id}, void();
   bool bl= cmp(xl, t->id, id), br= cmp(ub(xr), t->id, id);
   if (!bl && !br) return;
   if constexpr (persistent) t= new Node(*t);
   if (bl && br) return t->id= id, void();
   T xm= (xl + xr) / 2;
   if (cmp(xm, t->id, id)) std::swap(t->id, id), bl= !bl;
   if constexpr (std::is_floating_point_v<T>)
    if (xr - xl < 1e-9) return;
   bl ? addl(t->ch[0], id, xl, xm) : addl(t->ch[1], id, xm, xr);
  }
  inline void adds(Node *&t, int id, T l, T r, T xl, T xr) {
   if (r <= xl || xr <= l) return;
   if (l <= xl && xr <= r) return addl(t, id, xl, xr);
   if (!t) t= new Node;
   else if constexpr (persistent) t= new Node(*t);
   T xm= (xl + xr) / 2;
   adds(t->ch[0], id, l, r, xl, xm), adds(t->ch[1], id, l, r, xm, xr);
  }
  inline std::pair<R, int> query(const Node *t, T x, T xl, T xr) const {
   if (!t) return {R(), -1};
   T xm= (xl + xr) / 2;
   auto b= x < xm ? query(t->ch[0], x, xl, xm) : query(t->ch[1], x, xm, xr);
   if (t->id == -1) return b;
   R a= eval(t->id, x);
   return b.second != -1 && cmp(a, b.first, t->id, b.second) ? b : std::make_pair(a, t->id);
  }
 public:
  LiChaoTreeInterface()= default;
  LiChaoTreeInterface(LiChaoTree *ins): ins(ins), root(nullptr) {}
  void insert(const Prms &...args) { ins->ps.emplace_back(args...), addl(root, ins->ps.size() - 1, ins->LB, ins->UB); }
  // [l, r)
  void insert(const Prms &...args, T l, T r) {
   l= std::max(l, ins->LB), r= std::min(r, ins->UB);
   if (l < r) ins->ps.emplace_back(args...), adds(root, ins->ps.size() - 1, l, r, ins->LB, ins->UB);
  }
  // [l, UB)
  void insert(const Prms &...args, T l) { insert(args..., l, ins->UB); }
  std::pair<R, int> query(T x) const { return assert(ins->LB <= x && x < ins->UB), query(root, x, ins->LB, ins->UB); }
  const std::tuple<Prms...> &params(int id) const { return ins->ps[id]; }
 };
public:
 LiChaoTree(const F &f, T LB= -2e9, T UB= 2e9): f(f), LB(LB), UB(UB) {}
 template <MinMaxEnum sgn= MINIMIZE, bool persistent= false> LiChaoTreeInterface<sgn, persistent> make_tree() { return this; }
};
template <class F, class T, class U> LiChaoTree(F, T, U) -> LiChaoTree<F, argument_type_t<F>>;
template <class F, class T> LiChaoTree(F, T) -> LiChaoTree<F, argument_type_t<F>>;
template <class F> LiChaoTree(F) -> LiChaoTree<F, argument_type_t<F>>;
#line 8 "test/yukicoder/2332.zalgo.test.cpp"
using namespace std;
signed main() {
 cin.tie(0);
 ios::sync_with_stdio(0);
 int N, M;
 cin >> N >> M;
 vector<int> A(N), B(M), C(M);
 for (int i= 0; i < N; ++i) cin >> A[i];
 for (int i= 0; i < M; ++i) cin >> B[i];
 for (int i= 0; i < M; ++i) cin >> C[i];
 A.insert(A.end(), B.begin(), B.end());
 vector<int> Z= z_algorithm(A);
 Z= vector<int>(Z.begin() + N, Z.end());
 for (int &x: Z) x= min(x, N);
 auto f= [&](int x, long long a, long long b) { return a * x + b; };
 LiChaoTree lct(f, 0, 1e9 + 10);
 auto tree= lct.make_tree<MINIMIZE>();
 long long ans= 0;
 for (int i= 0; i < M; ++i) {
  if (ans >= 0) tree.insert(C[i], ans - (long long)C[i] * i, i + 1, i + Z[i] + 1);
  auto [a, b]= tree.query(i + 1);
  ans= b < 0 ? -1 : a;
 }
 cout << ans << '\n';
 return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++-13	sample_1.txt	AC	5 ms	4 MB
g++-13	sample_2.txt	AC	5 ms	4 MB
g++-13	test_1.txt	AC	5 ms	4 MB
g++-13	test_10.txt	AC	25 ms	6 MB
g++-13	test_11.txt	AC	49 ms	10 MB
g++-13	test_12.txt	AC	50 ms	10 MB
g++-13	test_13.txt	AC	50 ms	10 MB
g++-13	test_14.txt	AC	50 ms	9 MB
g++-13	test_15.txt	AC	49 ms	9 MB
g++-13	test_16.txt	AC	50 ms	10 MB
g++-13	test_17.txt	AC	50 ms	10 MB
g++-13	test_18.txt	AC	50 ms	10 MB
g++-13	test_19.txt	AC	49 ms	10 MB
g++-13	test_2.txt	AC	5 ms	4 MB
g++-13	test_20.txt	AC	49 ms	10 MB
g++-13	test_21.txt	AC	51 ms	10 MB
g++-13	test_22.txt	AC	51 ms	10 MB
g++-13	test_23.txt	AC	51 ms	10 MB
g++-13	test_24.txt	AC	51 ms	10 MB
g++-13	test_25.txt	AC	51 ms	10 MB
g++-13	test_26.txt	AC	54 ms	10 MB
g++-13	test_27.txt	AC	54 ms	10 MB
g++-13	test_28.txt	AC	54 ms	9 MB
g++-13	test_29.txt	AC	54 ms	10 MB
g++-13	test_3.txt	AC	5 ms	4 MB
g++-13	test_30.txt	AC	53 ms	9 MB
g++-13	test_31.txt	AC	64 ms	11 MB
g++-13	test_32.txt	AC	65 ms	11 MB
g++-13	test_33.txt	AC	65 ms	11 MB
g++-13	test_34.txt	AC	64 ms	11 MB
g++-13	test_35.txt	AC	65 ms	11 MB
g++-13	test_36.txt	AC	63 ms	11 MB
g++-13	test_37.txt	AC	64 ms	11 MB
g++-13	test_38.txt	AC	67 ms	12 MB
g++-13	test_39.txt	AC	63 ms	11 MB
g++-13	test_4.txt	AC	5 ms	4 MB
g++-13	test_40.txt	AC	61 ms	10 MB
g++-13	test_41.txt	AC	93 ms	17 MB
g++-13	test_42.txt	AC	90 ms	17 MB
g++-13	test_43.txt	AC	87 ms	17 MB
g++-13	test_44.txt	AC	92 ms	18 MB
g++-13	test_45.txt	AC	91 ms	18 MB
g++-13	test_46.txt	AC	127 ms	20 MB
g++-13	test_47.txt	AC	127 ms	20 MB
g++-13	test_48.txt	AC	127 ms	20 MB
g++-13	test_49.txt	AC	126 ms	20 MB
g++-13	test_5.txt	AC	5 ms	4 MB
g++-13	test_50.txt	AC	126 ms	20 MB
g++-13	test_51.txt	AC	56 ms	9 MB
g++-13	test_52.txt	AC	55 ms	10 MB
g++-13	test_53.txt	AC	54 ms	9 MB
g++-13	test_54.txt	AC	55 ms	10 MB
g++-13	test_55.txt	AC	56 ms	10 MB
g++-13	test_56.txt	AC	48 ms	10 MB
g++-13	test_57.txt	AC	47 ms	10 MB
g++-13	test_58.txt	AC	48 ms	9 MB
g++-13	test_59.txt	AC	49 ms	10 MB
g++-13	test_6.txt	AC	41 ms	8 MB
g++-13	test_60.txt	AC	48 ms	10 MB
g++-13	test_61.txt	AC	106 ms	19 MB
g++-13	test_7.txt	AC	17 ms	5 MB
g++-13	test_8.txt	AC	34 ms	8 MB
g++-13	test_9.txt	AC	35 ms	7 MB
clang++-18	sample_1.txt	AC	5 ms	4 MB
clang++-18	sample_2.txt	AC	5 ms	4 MB
clang++-18	test_1.txt	AC	5 ms	4 MB
clang++-18	test_10.txt	AC	27 ms	6 MB
clang++-18	test_11.txt	AC	52 ms	10 MB
clang++-18	test_12.txt	AC	52 ms	10 MB
clang++-18	test_13.txt	AC	52 ms	10 MB
clang++-18	test_14.txt	AC	53 ms	9 MB
clang++-18	test_15.txt	AC	52 ms	10 MB
clang++-18	test_16.txt	AC	52 ms	10 MB
clang++-18	test_17.txt	AC	53 ms	10 MB
clang++-18	test_18.txt	AC	52 ms	10 MB
clang++-18	test_19.txt	AC	52 ms	10 MB
clang++-18	test_2.txt	AC	5 ms	4 MB
clang++-18	test_20.txt	AC	52 ms	10 MB
clang++-18	test_21.txt	AC	55 ms	10 MB
clang++-18	test_22.txt	AC	55 ms	10 MB
clang++-18	test_23.txt	AC	55 ms	10 MB
clang++-18	test_24.txt	AC	54 ms	9 MB
clang++-18	test_25.txt	AC	57 ms	10 MB
clang++-18	test_26.txt	AC	58 ms	10 MB
clang++-18	test_27.txt	AC	57 ms	9 MB
clang++-18	test_28.txt	AC	57 ms	10 MB
clang++-18	test_29.txt	AC	57 ms	10 MB
clang++-18	test_3.txt	AC	5 ms	4 MB
clang++-18	test_30.txt	AC	57 ms	10 MB
clang++-18	test_31.txt	AC	67 ms	11 MB
clang++-18	test_32.txt	AC	68 ms	11 MB
clang++-18	test_33.txt	AC	68 ms	11 MB
clang++-18	test_34.txt	AC	68 ms	11 MB
clang++-18	test_35.txt	AC	67 ms	11 MB
clang++-18	test_36.txt	AC	66 ms	11 MB
clang++-18	test_37.txt	AC	67 ms	11 MB
clang++-18	test_38.txt	AC	71 ms	12 MB
clang++-18	test_39.txt	AC	67 ms	11 MB
clang++-18	test_4.txt	AC	5 ms	4 MB
clang++-18	test_40.txt	AC	65 ms	10 MB
clang++-18	test_41.txt	AC	93 ms	17 MB
clang++-18	test_42.txt	AC	94 ms	17 MB
clang++-18	test_43.txt	AC	91 ms	17 MB
clang++-18	test_44.txt	AC	96 ms	18 MB
clang++-18	test_45.txt	AC	94 ms	18 MB
clang++-18	test_46.txt	AC	132 ms	20 MB
clang++-18	test_47.txt	AC	132 ms	20 MB
clang++-18	test_48.txt	AC	132 ms	20 MB
clang++-18	test_49.txt	AC	132 ms	20 MB
clang++-18	test_5.txt	AC	5 ms	4 MB
clang++-18	test_50.txt	AC	131 ms	20 MB
clang++-18	test_51.txt	AC	59 ms	10 MB
clang++-18	test_52.txt	AC	58 ms	10 MB
clang++-18	test_53.txt	AC	57 ms	10 MB
clang++-18	test_54.txt	AC	59 ms	10 MB
clang++-18	test_55.txt	AC	60 ms	9 MB
clang++-18	test_56.txt	AC	51 ms	10 MB
clang++-18	test_57.txt	AC	51 ms	10 MB
clang++-18	test_58.txt	AC	51 ms	10 MB
clang++-18	test_59.txt	AC	51 ms	10 MB
clang++-18	test_6.txt	AC	44 ms	8 MB
clang++-18	test_60.txt	AC	51 ms	10 MB
clang++-18	test_61.txt	AC	112 ms	19 MB
clang++-18	test_7.txt	AC	17 ms	5 MB
clang++-18	test_8.txt	AC	36 ms	8 MB
clang++-18	test_9.txt	AC	38 ms	7 MB

Back to top page