結果

問題 No.2332 Make a Sequence
ユーザー shobonvip
提出日時 2023-05-28 15:54:37
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 428 ms / 2,000 ms
コード長 5,308 bytes
コンパイル時間 4,517 ms
コンパイル使用メモリ 263,296 KB
最終ジャッジ日時 2025-02-13 14:28:22
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef modint998244353 mint;
typedef long long ll;
// https://tjkendev.github.io/procon-library/cpp/convex_hull_trick/li_chao_tree_dynamic.html
class LiChaoTree {
struct Line {
ll a, b;
ll f(ll x) const { return a*x + b; }
Line(ll a, ll b) : a(a), b(b) {}
};
struct Node {
Node *left, *right;
Line line;
Node(Line line) : left(nullptr), right(nullptr), line(line) {}
};
const ll inf = 1e16L;
const Line inf_line = Line{0, inf};
Node* root;
ll xl, xr;
Node* _add_line(Node *nd, Line line, ll l, ll r) {
if(l == r) return nullptr;
ll m = (l + r) >> 1;
if(nd == nullptr) return new Node(line);
bool left = (line.f(l) <= nd->line.f(l));
bool mid = (line.f(m) <= nd->line.f(m));
bool right = (line.f(r) <= nd->line.f(r));
if(left && right) {
nd->line = line;
return nd;
}
if(!left && !right) {
return nd;
}
if(mid) {
swap(nd->line, line);
}
if(left != mid) {
nd->left = _add_line(nd->left, line, l, m);
} else {
nd->right = _add_line(nd->right, line, m, r);
}
return nd;
}
Node* _add_segment_line(ll a, ll b, Node *nd, Line line, ll l, ll r) {
if(r <= a || b <= l) {
return nd;
}
if(a <= l && r <= b) {
return _add_line(nd, line, l, r);
}
if(nd == nullptr) {
nd = new Node(inf_line);
}
ll m = (l + r) >> 1;
nd->left = _add_segment_line(a, b, nd->left, line, l, m);
nd->right = _add_segment_line(a, b, nd->right, line, m, r);
return nd;
}
ll _query(ll k, ll l, ll r) {
Node *nd = root;
ll s = inf;
while(r-l > 0 && nd != nullptr) {
ll m = (l + r) >> 1;
s = min(s, nd->line.f(k));
if(k < m) {
r = m;
nd = nd->left;
} else {
l = m;
nd = nd->right;
}
}
return s;
}
public:
// [xl, xr)
LiChaoTree(ll xl, ll xr) : xl(xl), xr(xr), root(nullptr) {}
void add_line(ll a, ll b) {
Line line = Line{a, b};
root = _add_line(root, line, xl, xr);
}
void add_segment_line(ll a, ll b, ll l, ll r) {
Line line = Line{a, b};
root = _add_segment_line(l, r, root, line, xl, xr);
}
ll query(ll x) {
return _query(x, xl, xr);
}
};
// isprime
bool isprime(ll n){
if (n == 1) return false;
for (ll i = 2; i * i <= n; i++){
if (n % i == 0) return false;
}
return true;
}
// importrandom
// don't forget randomjumon
// and also isprime
ll RandomMod(ll l, ll r){
ll ret = l + rand() % (r - l);
while (!isprime(ret)) ret = l + rand() % (r - l);
return ret;
}
ll randrange(ll l, ll r){
return l + rand() % (r - l);
}
// -----
// defcomp
template <typename T>
vector<T> compress(vector<T> &X) {
vector<T> vals = X;
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
return vals;
}
// -----
// importbisect
template <typename T>
int bisect_left(vector<T> &X, T v){
return lower_bound(X.begin(), X.end(), v) - X.begin();
}
template <typename T>
int bisect_right(vector<T> &X, T v){
return upper_bound(X.begin(), X.end(), v) - X.begin();
}
// -----
int main(){
srand((unsigned)time(NULL));
// Rolling Hash
typedef dynamic_modint<0> mint1;
typedef dynamic_modint<1> mint2;
int mod1 = RandomMod(7e8, 1e9);
int mod2 = RandomMod(7e8, 1e9);
mint1::set_mod(mod1);
mint2::set_mod(mod2);
mint1 b1 = randrange(100, 200);
mint2 b2 = randrange(100, 200);
int MAX_m = 1000000;
vector<mint1> b1l(MAX_m+1);
b1l[0] = 1;
for (int i=0; i<MAX_m; i++){
b1l[i+1] = b1l[i] * b1;
}
vector<mint2> b2l(MAX_m+1);
b2l[0] = 1;
for (int i=0; i<MAX_m; i++){
b2l[i+1] = b2l[i] * b2;
}
// -----
int n, m; cin >> n >> m;
vector<ll> a(n);
vector<ll> b(m);
vector<ll> c(m);
vector<ll> over;
for (int i=0; i<n; i++){
cin >> a[i];
over.push_back(a[i]);
}
for (int i=0; i<m; i++){
cin >> b[i];
over.push_back(b[i]);
}
for (int i=0; i<m; i++){
cin >> c[i];
}
vector<ll> p = compress(over);
vector<mint1> t1(n+1);
vector<mint2> t2(n+1);
{
mint1 x1 = 0;
mint2 x2 = 0;
for (int i=0; i<n; i++){
x1 = x1 * b1 + bisect_left(p, a[i]) + 1;
x2 = x2 * b2 + bisect_left(p, a[i]) + 1;
t1[i+1] = x1;
t2[i+1] = x2;
}
}
vector<mint1> u1(m+1);
vector<mint2> u2(m+1);
{
mint1 x1 = 0;
mint2 x2 = 0;
for (int i=0; i<m; i++){
x1 = x1 * b1 + bisect_left(p, b[i]) + 1;
x2 = x2 * b2 + bisect_left(p, b[i]) + 1;
u1[i+1] = x1;
u2[i+1] = x2;
}
}
vector<int> linemax(m);
for (int i=0; i<m; i++){
int ub = m+1;
int lb = i;
while (ub - lb > 1){
int targ = (ub + lb) / 2;
mint1 kt1 = t1[targ-i];
mint2 kt2 = t2[targ-i];
mint1 ku1 = u1[targ] - u1[i] * b1l[targ - i];
mint2 ku2 = u2[targ] - u2[i] * b2l[targ - i];
if (kt1 == ku1 && kt2 == ku2){
lb = targ;
}else{
ub = targ;
}
}
linemax[i] = lb;\
}
LiChaoTree lc(0, m+1);
vector<ll> dp(m+1, 1e18);
for (int i=0; i<m+1; i++){
ll val = 0;
if (i > 0){
val = lc.query(i);
}
dp[i] = val;
//cout << i << " " << val << endl;
if (i < m && linemax[i] > i){
lc.add_segment_line(c[i], dp[i] - i * c[i], i, linemax[i] + 1);
}
}
if (dp[m] >= 1e16) cout << -1 << endl;
else cout << dp[m] << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0