結果
問題 | No.2332 Make a Sequence |
ユーザー |
|
提出日時 | 2023-05-28 14:51:19 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 379 ms / 2,000 ms |
コード長 | 3,202 bytes |
コンパイル時間 | 2,038 ms |
コンパイル使用メモリ | 95,960 KB |
実行使用メモリ | 27,604 KB |
最終ジャッジ日時 | 2024-12-27 03:15:43 |
合計ジャッジ時間 | 24,663 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 61 |
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:132:9: warning: 'ans' may be used uninitialized [-Wmaybe-uninitialized] 132 | if(ans==(long)1e18)ans=-1; | ^~ main.cpp:121:14: note: 'ans' was declared here 121 | long ans; | ^~~
ソースコード
#include<iostream> #include<vector> #include<queue> #include<atcoder/string> using namespace std; /** * @brief Dynamic-Li-Chao-Tree * @docs docs/dynamic-li-chao-tree.md */ template< typename T, T x_low, T x_high, T id > struct DynamicLiChaoTree { struct Line { T a, b; Line(T a, T b) : a(a), b(b) {} inline T get(T x) const { return a * x + b; } }; struct Node { Line x; Node *l, *r; Node(const Line &x) : x{x}, l{nullptr}, r{nullptr} {} }; Node *root; DynamicLiChaoTree() : root{nullptr} {} Node *add_line(Node *t, Line &x, const T &l, const T &r, const T &x_l, const T &x_r) { if(!t) return new Node(x); T t_l = t->x.get(l), t_r = t->x.get(r); if(t_l <= x_l && t_r <= x_r) { return t; } else if(t_l >= x_l && t_r >= x_r) { t->x = x; return t; } else { T m = (l + r) / 2; if(m == r) --m; T t_m = t->x.get(m), x_m = x.get(m); if(t_m > x_m) { swap(t->x, x); if(x_l >= t_l) t->l = add_line(t->l, x, l, m, t_l, t_m); else t->r = add_line(t->r, x, m + 1, r, t_m + x.a, t_r); } else { if(t_l >= x_l) t->l = add_line(t->l, x, l, m, x_l, x_m); else t->r = add_line(t->r, x, m + 1, r, x_m + x.a, x_r); } return t; } } void add_line(const T &a, const T &b) { Line x(a, b); root = add_line(root, x, x_low, x_high, x.get(x_low), x.get(x_high)); } Node *add_segment(Node *t, Line &x, const T &a, const T &b, const T &l, const T &r, const T &x_l, const T &x_r) { if(r < a || b < l) return t; if(a <= l && r <= b) { Line y{x}; return add_line(t, y, l, r, x_l, x_r); } if(t) { T t_l = t->x.get(l), t_r = t->x.get(r); if(t_l <= x_l && t_r <= x_r) return t; } else { t = new Node(Line(0, id)); } T m = (l + r) / 2; if(m == r) --m; T x_m = x.get(m); t->l = add_segment(t->l, x, a, b, l, m, x_l, x_m); t->r = add_segment(t->r, x, a, b, m + 1, r, x_m + x.a, x_r); return t; } void add_segment(const T &l, const T &r, const T &a, const T &b) { Line x(a, b); root = add_segment(root, x, l, r - 1, x_low, x_high, x.get(x_low), x.get(x_high)); } T query(const Node *t, const T &l, const T &r, const T &x) const { if(!t) return id; if(l == r) return t->x.get(x); T m = (l + r) / 2; if(m == r) --m; if(x <= m) return min(t->x.get(x), query(t->l, l, m, x)); else return min(t->x.get(x), query(t->r, m + 1, r, x)); } T query(const T &x) const { return query(root, x_low, x_high, x); } }; int N,M; int A[2<<17],B[2<<17],C[2<<17]; int main() { cin>>N>>M; vector<int>S; for(int i=0;i<N;i++) { cin>>A[i]; S.push_back(A[i]); } for(int i=0;i<M;i++) { cin>>B[i]; S.push_back(B[i]); } for(int i=0;i<M;i++)cin>>C[i]; vector<int>T=atcoder::z_algorithm(S); DynamicLiChaoTree<long,0L,(long)2e5,(long)1e18>Q; Q.add_segment(0,1,0,0); long ans; for(int i=0;i<=M;i++) { ans=Q.query(i); if(i<M&&ans<(long)1e18) { int len=min(T[N+i],N); //cout<<i<<"->"<<i+len<<" : "<<ans+C[i]<<endl; Q.add_segment(i,i+len+1,C[i],ans-(long)i*C[i]); } } if(ans==(long)1e18)ans=-1; cout<<ans<<endl; }