結果
| 問題 | No.2332 Make a Sequence |
| ユーザー |
 NyaanNyaan
|
| 提出日時 | 2023-05-28 14:03:30 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 291 ms / 2,000 ms |
| コード長 | 22,545 bytes |
| コンパイル時間 | 5,353 ms |
| コンパイル使用メモリ | 285,808 KB |
| 実行使用メモリ | 62,028 KB |
| 最終ジャッジ日時 | 2023-08-27 08:56:06 |
| 合計ジャッジ時間 | 23,646 ms |
|
ジャッジサーバーID （参考情報） |
judge15 / judge11 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
4,380 KB |
| testcase_01 | AC | 1 ms
4,376 KB |
| testcase_02 | AC | 1 ms
4,380 KB |
| testcase_03 | AC | 2 ms
4,376 KB |
| testcase_04 | AC | 1 ms
4,380 KB |
| testcase_05 | AC | 2 ms
4,376 KB |
| testcase_06 | AC | 1 ms
4,380 KB |
| testcase_07 | AC | 227 ms
52,460 KB |
| testcase_08 | AC | 83 ms
21,644 KB |
| testcase_09 | AC | 187 ms
41,064 KB |
| testcase_10 | AC | 156 ms
37,436 KB |
| testcase_11 | AC | 110 ms
25,544 KB |
| testcase_12 | AC | 289 ms
60,212 KB |
| testcase_13 | AC | 288 ms
60,232 KB |
| testcase_14 | AC | 290 ms
60,196 KB |
| testcase_15 | AC | 289 ms
60,284 KB |
| testcase_16 | AC | 286 ms
60,332 KB |
| testcase_17 | AC | 290 ms
60,404 KB |
| testcase_18 | AC | 282 ms
60,188 KB |
| testcase_19 | AC | 291 ms
60,792 KB |
| testcase_20 | AC | 289 ms
60,596 KB |
| testcase_21 | AC | 284 ms
60,444 KB |
| testcase_22 | AC | 271 ms
60,424 KB |
| testcase_23 | AC | 270 ms
60,192 KB |
| testcase_24 | AC | 271 ms
60,180 KB |
| testcase_25 | AC | 267 ms
59,240 KB |
| testcase_26 | AC | 269 ms
60,280 KB |
| testcase_27 | AC | 261 ms
60,548 KB |
| testcase_28 | AC | 264 ms
60,072 KB |
| testcase_29 | AC | 262 ms
60,188 KB |
| testcase_30 | AC | 258 ms
60,204 KB |
| testcase_31 | AC | 260 ms
60,412 KB |
| testcase_32 | AC | 260 ms
59,180 KB |
| testcase_33 | AC | 258 ms
59,308 KB |
| testcase_34 | AC | 259 ms
59,436 KB |
| testcase_35 | AC | 257 ms
60,012 KB |
| testcase_36 | AC | 261 ms
59,484 KB |
| testcase_37 | AC | 237 ms
59,564 KB |
| testcase_38 | AC | 238 ms
59,688 KB |
| testcase_39 | AC | 232 ms
59,276 KB |
| testcase_40 | AC | 234 ms
59,596 KB |
| testcase_41 | AC | 235 ms
60,284 KB |
| testcase_42 | AC | 233 ms
61,660 KB |
| testcase_43 | AC | 234 ms
62,028 KB |
| testcase_44 | AC | 227 ms
61,820 KB |
| testcase_45 | AC | 229 ms
61,564 KB |
| testcase_46 | AC | 229 ms
61,696 KB |
| testcase_47 | AC | 211 ms
59,052 KB |
| testcase_48 | AC | 212 ms
59,344 KB |
| testcase_49 | AC | 214 ms
59,276 KB |
| testcase_50 | AC | 213 ms
59,320 KB |
| testcase_51 | AC | 211 ms
59,356 KB |
| testcase_52 | AC | 238 ms
60,336 KB |
| testcase_53 | AC | 245 ms
60,072 KB |
| testcase_54 | AC | 244 ms
60,340 KB |
| testcase_55 | AC | 241 ms
60,064 KB |
| testcase_56 | AC | 242 ms
60,668 KB |
| testcase_57 | AC | 201 ms
60,480 KB |
| testcase_58 | AC | 194 ms
60,212 KB |
| testcase_59 | AC | 197 ms
60,288 KB |
| testcase_60 | AC | 195 ms
59,244 KB |
| testcase_61 | AC | 194 ms
59,000 KB |
| testcase_62 | AC | 206 ms
59,360 KB |
ソースコード
/**
* date : 2023-05-28 14:03:26
* author : Nyaan
*/
#define NDEBUG
using namespace std;
// intrinstic
#include <immintrin.h>
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cfenv>
#include <cfloat>
#include <chrono>
#include <cinttypes>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdarg>
#include <cstddef>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <streambuf>
#include <string>
#include <tuple>
#include <type_traits>
#include <typeinfo>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// utility
namespace Nyaan {
using ll = long long;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = vector<vector<T>>;
using vi = vector<int>;
using vl = vector<long long>;
using vd = V<double>;
using vs = V<string>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long long>>;
template <typename T, typename U>
struct P : pair<T, U> {
template <typename... Args>
P(Args... args) : pair<T, U>(args...) {}
using pair<T, U>::first;
using pair<T, U>::second;
P &operator+=(const P &r) {
first += r.first;
second += r.second;
return *this;
}
P &operator-=(const P &r) {
first -= r.first;
second -= r.second;
return *this;
}
P &operator*=(const P &r) {
first *= r.first;
second *= r.second;
return *this;
}
template <typename S>
P &operator*=(const S &r) {
first *= r, second *= r;
return *this;
}
P operator+(const P &r) const { return P(*this) += r; }
P operator-(const P &r) const { return P(*this) -= r; }
P operator*(const P &r) const { return P(*this) *= r; }
template <typename S>
P operator*(const S &r) const {
return P(*this) *= r;
}
P operator-() const { return P{-first, -second}; }
};
using pl = P<ll, ll>;
using pi = P<int, int>;
using vp = V<pl>;
constexpr int inf = 1001001001;
constexpr long long infLL = 4004004004004004004LL;
template <typename T>
int sz(const T &t) {
return t.size();
}
template <typename T, typename U>
inline bool amin(T &x, U y) {
return (y < x) ? (x = y, true) : false;
}
template <typename T, typename U>
inline bool amax(T &x, U y) {
return (x < y) ? (x = y, true) : false;
}
template <typename T>
inline T Max(const vector<T> &v) {
return *max_element(begin(v), end(v));
}
template <typename T>
inline T Min(const vector<T> &v) {
return *min_element(begin(v), end(v));
}
template <typename T>
inline long long Sum(const vector<T> &v) {
return accumulate(begin(v), end(v), 0LL);
}
template <typename T>
int lb(const vector<T> &v, const T &a) {
return lower_bound(begin(v), end(v), a) - begin(v);
}
template <typename T>
int ub(const vector<T> &v, const T &a) {
return upper_bound(begin(v), end(v), a) - begin(v);
}
constexpr long long TEN(int n) {
long long ret = 1, x = 10;
for (; n; x *= x, n >>= 1) ret *= (n & 1 ? x : 1);
return ret;
}
template <typename T, typename U>
pair<T, U> mkp(const T &t, const U &u) {
return make_pair(t, u);
}
template <typename T>
vector<T> mkrui(const vector<T> &v, bool rev = false) {
vector<T> ret(v.size() + 1);
if (rev) {
for (int i = int(v.size()) - 1; i >= 0; i--) ret[i] = v[i] + ret[i + 1];
} else {
for (int i = 0; i < int(v.size()); i++) ret[i + 1] = ret[i] + v[i];
}
return ret;
};
template <typename T>
vector<T> mkuni(const vector<T> &v) {
vector<T> ret(v);
sort(ret.begin(), ret.end());
ret.erase(unique(ret.begin(), ret.end()), ret.end());
return ret;
}
template <typename F>
vector<int> mkord(int N,F f) {
vector<int> ord(N);
iota(begin(ord), end(ord), 0);
sort(begin(ord), end(ord), f);
return ord;
}
template <typename T>
vector<int> mkinv(vector<T> &v) {
int max_val = *max_element(begin(v), end(v));
vector<int> inv(max_val + 1, -1);
for (int i = 0; i < (int)v.size(); i++) inv[v[i]] = i;
return inv;
}
vector<int> mkiota(int n) {
vector<int> ret(n);
iota(begin(ret), end(ret), 0);
return ret;
}
template <typename T>
T mkrev(const T &v) {
T w{v};
reverse(begin(w), end(w));
return w;
}
template <typename T>
bool nxp(vector<T> &v) {
return next_permutation(begin(v), end(v));
}
template <typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
} // namespace Nyaan
// bit operation
namespace Nyaan {
__attribute__((target("popcnt"))) inline int popcnt(const u64 &a) {
return _mm_popcnt_u64(a);
}
inline int lsb(const u64 &a) { return a ? __builtin_ctzll(a) : 64; }
inline int ctz(const u64 &a) { return a ? __builtin_ctzll(a) : 64; }
inline int msb(const u64 &a) { return a ? 63 - __builtin_clzll(a) : -1; }
template <typename T>
inline int gbit(const T &a, int i) {
return (a >> i) & 1;
}
template <typename T>
inline void sbit(T &a, int i, bool b) {
if (gbit(a, i) != b) a ^= T(1) << i;
}
constexpr long long PW(int n) { return 1LL << n; }
constexpr long long MSK(int n) { return (1LL << n) - 1; }
} // namespace Nyaan
// inout
namespace Nyaan {
template <typename T, typename U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
os << p.first << " " << p.second;
return os;
}
template <typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p) {
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
int s = (int)v.size();
for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i];
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
for (auto &x : v) is >> x;
return is;
}
istream &operator>>(istream &is, __int128_t &x) {
string S;
is >> S;
x = 0;
int flag = 0;
for (auto &c : S) {
if (c == '-') {
flag = true;
continue;
}
x *= 10;
x += c - '0';
}
if (flag) x = -x;
return is;
}
istream &operator>>(istream &is, __uint128_t &x) {
string S;
is >> S;
x = 0;
for (auto &c : S) {
x *= 10;
x += c - '0';
}
return is;
}
ostream &operator<<(ostream &os, __int128_t x) {
if (x == 0) return os << 0;
if (x < 0) os << '-', x = -x;
string S;
while (x) S.push_back('0' + x % 10), x /= 10;
reverse(begin(S), end(S));
return os << S;
}
ostream &operator<<(ostream &os, __uint128_t x) {
if (x == 0) return os << 0;
string S;
while (x) S.push_back('0' + x % 10), x /= 10;
reverse(begin(S), end(S));
return os << S;
}
void in() {}
template <typename T, class... U>
void in(T &t, U &...u) {
cin >> t;
in(u...);
}
void out() { cout << "\n"; }
template <typename T, class... U, char sep = ' '>
void out(const T &t, const U &...u) {
cout << t;
if (sizeof...(u)) cout << sep;
out(u...);
}
struct IoSetupNya {
IoSetupNya() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(15);
cerr << fixed << setprecision(7);
}
} iosetupnya;
} // namespace Nyaan
// debug
#ifdef NyaanDebug
#define trc(...) (void(0))
#else
#define trc(...) (void(0))
#endif
#ifdef NyaanLocal
#define trc2(...) (void(0))
#else
#define trc2(...) (void(0))
#endif
// macro
#define each(x, v) for (auto&& x : v)
#define each2(x, y, v) for (auto&& [x, y] : v)
#define all(v) (v).begin(), (v).end()
#define rep(i, N) for (long long i = 0; i < (long long)(N); i++)
#define repr(i, N) for (long long i = (long long)(N)-1; i >= 0; i--)
#define rep1(i, N) for (long long i = 1; i <= (long long)(N); i++)
#define repr1(i, N) for (long long i = (N); (long long)(i) > 0; i--)
#define reg(i, a, b) for (long long i = (a); i < (b); i++)
#define regr(i, a, b) for (long long i = (b)-1; i >= (a); i--)
#define fi first
#define se second
#define ini(...) \
int __VA_ARGS__; \
in(__VA_ARGS__)
#define inl(...) \
long long __VA_ARGS__; \
in(__VA_ARGS__)
#define ins(...) \
string __VA_ARGS__; \
in(__VA_ARGS__)
#define in2(s, t) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i]); \
}
#define in3(s, t, u) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i], u[i]); \
}
#define in4(s, t, u, v) \
for (int i = 0; i < (int)s.size(); i++) { \
in(s[i], t[i], u[i], v[i]); \
}
#define die(...) \
do { \
Nyaan::out(__VA_ARGS__); \
return; \
} while (0)
namespace Nyaan {
void solve();
}
int main() { Nyaan::solve(); }
//
template <typename T, T INF>
struct LiChaoTree {
struct Line {
T slope, intercept;
Line(T slope, T intercept) : slope(slope), intercept(intercept) {}
inline T get(T x) const { return slope * x + intercept; }
inline bool over(const Line &other, const T &x) const {
return get(x) < other.get(x);
}
};
// remind セグ木は0-indexedの実装
vector<T> xset;
vector<Line> seg;
int _size;
// 引数xにはx座標の集合を入れる
LiChaoTree(const vector<T> &x) : xset(x) {
sort(xset.begin(), xset.end());
xset.erase(unique(xset.begin(), xset.end()), xset.end());
_size = 1;
while (_size < (int)xset.size()) _size <<= 1;
while ((int)xset.size() < _size) xset.push_back(xset.back() + 1);
seg.assign(2 * _size, Line(0, INF));
}
// 以上 xset[max]以下であることを仮定
int get_more_idx(T k) {
return lower_bound(xset.begin(), xset.end(), k) - xset.begin();
}
// 以下 xset[0]以上であることを仮定
int get_less_idx(T k) {
int ret = upper_bound(xset.begin(), xset.end(), k) - xset.begin();
return max(0, ret - 1);
}
// 内部用
void inner_update(T a, T b, int left, int right, int seg_idx) {
Line line(a, b);
while (1) {
int mid = (left + right) >> 1;
bool l_over = line.over(seg[seg_idx], xset[left]);
bool r_over = line.over(seg[seg_idx], xset[right - 1]);
if (l_over == r_over) {
if (l_over) swap(seg[seg_idx], line);
return;
}
bool m_over = line.over(seg[seg_idx], xset[mid]);
if (m_over) swap(seg[seg_idx], line);
if (l_over != m_over)
seg_idx = (seg_idx << 1), right = mid;
else
seg_idx = (seg_idx << 1) | 1, left = mid;
}
}
// 内部用
void inner_update(T a, T b, int seg_idx) {
int left, right;
int upper_bit = 31 - __builtin_clz(seg_idx);
left = (_size >> upper_bit) * (seg_idx - (1 << upper_bit));
right = left + (_size >> upper_bit);
inner_update(a, b, left, right, seg_idx);
}
// y = ax + bなる直線を追加
void update(T a, T b) { inner_update(a, b, 0, _size, 1); }
// 閉区間x in [left , right]に線分y = ax + bを追加するクエリ
void update_segment(T a, T b, T low, T high) {
int left = get_more_idx(low) + _size;
int right = get_less_idx(high) + _size + 1;
for (; left < right; left >>= 1, right >>= 1) {
if (left & 1) inner_update(a, b, left++);
if (right & 1) inner_update(a, b, --right);
}
}
T inner_query(int x, int segidx) {
T ret = seg[segidx].get(x);
while (segidx > 1) {
segidx = segidx >> 1;
ret = min(ret, seg[segidx].get(x));
}
return ret;
}
// x = xset[k]なる点における最小値クエリ
T query_idx(int k) {
const T x = xset[k];
k += _size;
return inner_query(x, k);
}
// xにおける最小クエリ
T query(T x) { return query_idx(get_more_idx(x)); }
};
namespace atcoder {
namespace internal {
std::vector<int> sa_naive(const std::vector<int>& s) {
int n = int(s.size());
std::vector<int> sa(n);
std::iota(sa.begin(), sa.end(), 0);
std::sort(sa.begin(), sa.end(), [&](int l, int r) {
if (l == r) return false;
while (l < n && r < n) {
if (s[l] != s[r]) return s[l] < s[r];
l++;
r++;
}
return l == n;
});
return sa;
}
std::vector<int> sa_doubling(const std::vector<int>& s) {
int n = int(s.size());
std::vector<int> sa(n), rnk = s, tmp(n);
std::iota(sa.begin(), sa.end(), 0);
for (int k = 1; k < n; k *= 2) {
auto cmp = [&](int x, int y) {
if (rnk[x] != rnk[y]) return rnk[x] < rnk[y];
int rx = x + k < n ? rnk[x + k] : -1;
int ry = y + k < n ? rnk[y + k] : -1;
return rx < ry;
};
std::sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++) {
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
}
std::swap(tmp, rnk);
}
return sa;
}
// SA-IS, linear-time suffix array construction
// Reference:
// G. Nong, S. Zhang, and W. H. Chan,
// Two Efficient Algorithms for Linear Time Suffix Array Construction
template <int THRESHOLD_NAIVE = 10, int THRESHOLD_DOUBLING = 40>
std::vector<int> sa_is(const std::vector<int>& s, int upper) {
int n = int(s.size());
if (n == 0) return {};
if (n == 1) return {0};
if (n == 2) {
if (s[0] < s[1]) {
return {0, 1};
} else {
return {1, 0};
}
}
if (n < THRESHOLD_NAIVE) {
return sa_naive(s);
}
if (n < THRESHOLD_DOUBLING) {
return sa_doubling(s);
}
std::vector<int> sa(n);
std::vector<bool> ls(n);
for (int i = n - 2; i >= 0; i--) {
ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
}
std::vector<int> sum_l(upper + 1), sum_s(upper + 1);
for (int i = 0; i < n; i++) {
if (!ls[i]) {
sum_s[s[i]]++;
} else {
sum_l[s[i] + 1]++;
}
}
for (int i = 0; i <= upper; i++) {
sum_s[i] += sum_l[i];
if (i < upper) sum_l[i + 1] += sum_s[i];
}
auto induce = [&](const std::vector<int>& lms) {
std::fill(sa.begin(), sa.end(), -1);
std::vector<int> buf(upper + 1);
std::copy(sum_s.begin(), sum_s.end(), buf.begin());
for (auto d : lms) {
if (d == n) continue;
sa[buf[s[d]]++] = d;
}
std::copy(sum_l.begin(), sum_l.end(), buf.begin());
sa[buf[s[n - 1]]++] = n - 1;
for (int i = 0; i < n; i++) {
int v = sa[i];
if (v >= 1 && !ls[v - 1]) {
sa[buf[s[v - 1]]++] = v - 1;
}
}
std::copy(sum_l.begin(), sum_l.end(), buf.begin());
for (int i = n - 1; i >= 0; i--) {
int v = sa[i];
if (v >= 1 && ls[v - 1]) {
sa[--buf[s[v - 1] + 1]] = v - 1;
}
}
};
std::vector<int> lms_map(n + 1, -1);
int m = 0;
for (int i = 1; i < n; i++) {
if (!ls[i - 1] && ls[i]) {
lms_map[i] = m++;
}
}
std::vector<int> lms;
lms.reserve(m);
for (int i = 1; i < n; i++) {
if (!ls[i - 1] && ls[i]) {
lms.push_back(i);
}
}
induce(lms);
if (m) {
std::vector<int> sorted_lms;
sorted_lms.reserve(m);
for (int v : sa) {
if (lms_map[v] != -1) sorted_lms.push_back(v);
}
std::vector<int> rec_s(m);
int rec_upper = 0;
rec_s[lms_map[sorted_lms[0]]] = 0;
for (int i = 1; i < m; i++) {
int l = sorted_lms[i - 1], r = sorted_lms[i];
int end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n;
int end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n;
bool same = true;
if (end_l - l != end_r - r) {
same = false;
} else {
while (l < end_l) {
if (s[l] != s[r]) {
break;
}
l++;
r++;
}
if (l == n || s[l] != s[r]) same = false;
}
if (!same) rec_upper++;
rec_s[lms_map[sorted_lms[i]]] = rec_upper;
}
auto rec_sa =
sa_is<THRESHOLD_NAIVE, THRESHOLD_DOUBLING>(rec_s, rec_upper);
for (int i = 0; i < m; i++) {
sorted_lms[i] = lms[rec_sa[i]];
}
induce(sorted_lms);
}
return sa;
}
} // namespace internal
std::vector<int> suffix_array(const std::vector<int>& s, int upper) {
assert(0 <= upper);
for (int d : s) {
assert(0 <= d && d <= upper);
}
auto sa = internal::sa_is(s, upper);
return sa;
}
template <class T> std::vector<int> suffix_array(const std::vector<T>& s) {
int n = int(s.size());
std::vector<int> idx(n);
iota(idx.begin(), idx.end(), 0);
sort(idx.begin(), idx.end(), [&](int l, int r) { return s[l] < s[r]; });
std::vector<int> s2(n);
int now = 0;
for (int i = 0; i < n; i++) {
if (i && s[idx[i - 1]] != s[idx[i]]) now++;
s2[idx[i]] = now;
}
return internal::sa_is(s2, now);
}
std::vector<int> suffix_array(const std::string& s) {
int n = int(s.size());
std::vector<int> s2(n);
for (int i = 0; i < n; i++) {
s2[i] = s[i];
}
return internal::sa_is(s2, 255);
}
// Reference:
// T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park,
// Linear-Time Longest-Common-Prefix Computation in Suffix Arrays and Its
// Applications
template <class T>
std::vector<int> lcp_array(const std::vector<T>& s,
const std::vector<int>& sa) {
int n = int(s.size());
assert(n >= 1);
std::vector<int> rnk(n);
for (int i = 0; i < n; i++) {
rnk[sa[i]] = i;
}
std::vector<int> lcp(n - 1);
int h = 0;
for (int i = 0; i < n; i++) {
if (h > 0) h--;
if (rnk[i] == 0) continue;
int j = sa[rnk[i] - 1];
for (; j + h < n && i + h < n; h++) {
if (s[j + h] != s[i + h]) break;
}
lcp[rnk[i] - 1] = h;
}
return lcp;
}
std::vector<int> lcp_array(const std::string& s, const std::vector<int>& sa) {
int n = int(s.size());
std::vector<int> s2(n);
for (int i = 0; i < n; i++) {
s2[i] = s[i];
}
return lcp_array(s2, sa);
}
// Reference:
// D. Gusfield,
// Algorithms on Strings, Trees, and Sequences: Computer Science and
// Computational Biology
template <class T> std::vector<int> z_algorithm(const std::vector<T>& s) {
int n = int(s.size());
if (n == 0) return {};
std::vector<int> z(n);
z[0] = 0;
for (int i = 1, j = 0; i < n; i++) {
int& k = z[i];
k = (j + z[j] <= i) ? 0 : std::min(j + z[j] - i, z[i - j]);
while (i + k < n && s[k] == s[i + k]) k++;
if (j + z[j] < i + z[i]) j = i;
}
z[0] = n;
return z;
}
std::vector<int> z_algorithm(const std::string& s) {
int n = int(s.size());
std::vector<int> s2(n);
for (int i = 0; i < n; i++) {
s2[i] = s[i];
}
return z_algorithm(s2);
}
} // namespace atcoder
using namespace std;
template <typename T>
struct SparseTable {
inline static constexpr T INF = numeric_limits<T>::max() / 2;
int N;
vector<vector<T> > table;
T f(T a, T b) { return min(a, b); }
SparseTable() {}
SparseTable(const vector<T> &v) : N(v.size()) {
int b = 1;
while ((1 << b) <= N) ++b;
table.push_back(v);
for (int i = 1; i < b; i++) {
table.push_back(vector<T>(N, INF));
for (int j = 0; j + (1 << i) <= N; j++) {
table[i][j] = f(table[i - 1][j], table[i - 1][j + (1 << (i - 1))]);
}
}
}
// [l, r)
T query(int l, int r) {
assert(0 <= l and l <= r and r <= N);
if (l == r) return INF;
int b = 31 - __builtin_clz(r - l);
return f(table[b][l], table[b][r - (1 << b)]);
}
};
/**
* @brief Sparse Table
*/
template <typename Container>
struct StringSearch {
const Container& S;
int N;
vector<int> sa, la, invsa;
SparseTable<int> sparse;
StringSearch(const Container& _s) : S(_s), N(S.size()) {
sa = atcoder::suffix_array(S);
la = atcoder::lcp_array(S, sa);
invsa.resize(N);
for (int i = 0; i < N; i++) invsa[sa[i]] = i;
sparse = SparseTable<int>{la};
}
// lcp(s[i, N), s[j, N))
int lcp(int i, int j) {
assert(0 <= min(i, j) and max(i, j) < N);
if (i == j) return N - i;
int x = min(invsa[i], invsa[j]);
int y = max(invsa[i], invsa[j]);
return sparse.query(x, y);
}
// lcp(s[a, b), s[c, d))
int lcp(int a, int b, int c, int d) {
assert(0 <= a and a <= b and b <= N);
assert(0 <= c and c <= d and d <= N);
int l = lcp(a, c);
return min({l, b - a, d - c});
}
// lcp(s[a, b), s[c, d))
template <typename Int>
int lcp(pair<Int, Int> p, pair<Int, Int> q) {
return lcp(p.first, p.second, q.first, q.second);
}
// s[i, N) > s[j, N) : 1
// s[i, N) = s[j, N) : 0
// s[i, N) < s[j, N) : -1
int strcmp(int i, int j) {
assert(0 <= min(i, j) and max(i, j) < N);
if (i == j) return 0;
return invsa[i] < invsa[j] ? -1 : 1;
}
// s[a, b) > s[c, d) : 1
// s[a, b) = s[c, d) : 0
// s[a, b) < s[c, d) : -1
int strcmp(int a, int b, int c, int d) {
int l = lcp(a, b, c, d);
return a + l == b ? (c + l == d ? 0 : -1)
: c + l == d ? 1
: S[a + l] < S[c + l] ? -1
: 1;
}
// s[a, b) > s[c, d) : 1
// s[a, b) = s[c, d) : 0
// s[a, b) < s[c, d) : -1
template <typename Int>
int strcmp(pair<Int, Int> p, pair<Int, Int> q) {
return strcmp(p.first, p.second, q.first, q.second);
}
};
using namespace Nyaan;
void q() {
inl(N, M);
vl A(N), B(M), C(M);
in(A, B, C);
vl S = A;
rep(i, M) S.push_back(B[i]);
StringSearch ss{S};
vl xs;
rep(i, M + 1) xs.push_back(i);
LiChaoTree<ll, infLL> lct(xs);
vl dp(M + 1, infLL);
dp[0] = 0;
rep(i, M) {
if (dp[i] == infLL) continue;
int lcp = ss.lcp(0, N + i);
lct.update_segment(C[i], dp[i] - C[i] * i, i, i + lcp);
dp[i + 1] = lct.query(i + 1);
}
trc(dp);
ll ans = dp[M];
if (ans > TEN(15)) ans = -1;
out(ans);
}
void Nyaan::solve() {
int t = 1;
// in(t);
while (t--) q();
}