結果
問題 | No.2332 Make a Sequence |
ユーザー | momoyuu |
提出日時 | 2023-05-28 15:16:58 |
言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 608 ms / 2,000 ms |
コード長 | 4,456 bytes |
コンパイル時間 | 2,947 ms |
コンパイル使用メモリ | 251,752 KB |
実行使用メモリ | 35,900 KB |
最終ジャッジ日時 | 2023-08-27 11:51:09 |
合計ジャッジ時間 | 34,061 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 2 ms
4,380 KB |
testcase_03 | AC | 1 ms
4,380 KB |
testcase_04 | AC | 1 ms
4,376 KB |
testcase_05 | AC | 1 ms
4,376 KB |
testcase_06 | AC | 1 ms
4,376 KB |
testcase_07 | AC | 370 ms
18,144 KB |
testcase_08 | AC | 88 ms
10,144 KB |
testcase_09 | AC | 284 ms
15,964 KB |
testcase_10 | AC | 308 ms
13,664 KB |
testcase_11 | AC | 216 ms
10,452 KB |
testcase_12 | AC | 451 ms
21,776 KB |
testcase_13 | AC | 450 ms
21,724 KB |
testcase_14 | AC | 450 ms
21,904 KB |
testcase_15 | AC | 451 ms
21,808 KB |
testcase_16 | AC | 453 ms
21,736 KB |
testcase_17 | AC | 451 ms
22,064 KB |
testcase_18 | AC | 453 ms
21,724 KB |
testcase_19 | AC | 451 ms
21,912 KB |
testcase_20 | AC | 451 ms
21,720 KB |
testcase_21 | AC | 451 ms
21,772 KB |
testcase_22 | AC | 456 ms
22,056 KB |
testcase_23 | AC | 456 ms
21,996 KB |
testcase_24 | AC | 458 ms
22,044 KB |
testcase_25 | AC | 455 ms
22,040 KB |
testcase_26 | AC | 457 ms
22,164 KB |
testcase_27 | AC | 463 ms
22,844 KB |
testcase_28 | AC | 461 ms
22,872 KB |
testcase_29 | AC | 464 ms
22,844 KB |
testcase_30 | AC | 462 ms
23,000 KB |
testcase_31 | AC | 462 ms
22,780 KB |
testcase_32 | AC | 483 ms
27,044 KB |
testcase_33 | AC | 482 ms
27,044 KB |
testcase_34 | AC | 482 ms
27,004 KB |
testcase_35 | AC | 484 ms
27,008 KB |
testcase_36 | AC | 485 ms
27,152 KB |
testcase_37 | AC | 483 ms
26,740 KB |
testcase_38 | AC | 482 ms
27,112 KB |
testcase_39 | AC | 488 ms
28,332 KB |
testcase_40 | AC | 478 ms
26,480 KB |
testcase_41 | AC | 475 ms
26,120 KB |
testcase_42 | AC | 529 ms
34,440 KB |
testcase_43 | AC | 528 ms
34,432 KB |
testcase_44 | AC | 522 ms
34,200 KB |
testcase_45 | AC | 523 ms
34,916 KB |
testcase_46 | AC | 527 ms
34,968 KB |
testcase_47 | AC | 598 ms
35,900 KB |
testcase_48 | AC | 603 ms
35,816 KB |
testcase_49 | AC | 598 ms
35,844 KB |
testcase_50 | AC | 602 ms
35,808 KB |
testcase_51 | AC | 608 ms
35,768 KB |
testcase_52 | AC | 467 ms
24,016 KB |
testcase_53 | AC | 463 ms
23,176 KB |
testcase_54 | AC | 462 ms
22,776 KB |
testcase_55 | AC | 466 ms
23,748 KB |
testcase_56 | AC | 466 ms
23,880 KB |
testcase_57 | AC | 465 ms
22,956 KB |
testcase_58 | AC | 462 ms
22,784 KB |
testcase_59 | AC | 462 ms
22,956 KB |
testcase_60 | AC | 466 ms
23,652 KB |
testcase_61 | AC | 464 ms
22,928 KB |
testcase_62 | AC | 553 ms
32,632 KB |
ソースコード
#include<bits/stdc++.h> using namespace std; using ll = long long; /** * @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); } }; const ll m2 = 1000000007; const ll b2 = 1009; const ll m3 = 1000000009; const ll b3 = 2009; const ll m4 = 2147483587; const ll b4 = 2147483583; //https://gist.github.com/privet-kitty/295ac9202b7abb3039b493f8238bf40f#file-modulus-random-base-pair64-txt struct rhash{ int n; ll mod,B; vector<ll> sum; vector<ll> powb; rhash(){}; rhash(vector<ll> &s,ll mod,ll B):mod(mod),B(B){ n = s.size(); sum = vector<ll>(n+1,0); powb = vector<ll>(n+1,1); for(int i = 0;i<n;i++){ sum[i+1] = (sum[i]*B%mod+(s[i]))%mod; powb[i+1] = (powb[i]*B)%mod; } } ll get(int l,int r){ ll tmp = sum[r] - sum[l]*powb[r-l]%mod; if(tmp<0) tmp += mod; return tmp; } }; int main(){ int n,m; cin>>n>>m; vector<ll> 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]; vector<rhash> rs(2); vector<rhash> rrs(2); rs[0] = rhash(a,m2,b2); rs[1] = rhash(a,m3,b3); rrs[0] = rhash(b,m2,b2); rrs[1] = rhash(b,m3,b3); vector<ll> dp(m+1,1e16); dp[0] = 0; DynamicLiChaoTree<ll,0ll,(ll)2<<17,(ll)1e18> li; for(int i = 0;i<=m;i++){ if(i!=0) dp[i] = min(dp[i],li.query(i)); if(i==m) break; int right = min(m-i,n) + 1; int left = 0; while(right-left>1){ int mid = (right+left)/2; int ri = i + mid; bool ok = true; for(int j = 0;j<2;j++){ if(rs[j].get(0,mid)!=rrs[j].get(i,ri)) ok = false; } if(ok) left = mid; else right = mid; } //cout<<i<<" "<<left<<endl; //cout<<dp[i]<<endl; if(left==0) continue; li.add_segment(i,i+right,c[i],dp[i]-i*c[i]); } if(dp[m]==1e16) cout<<-1<<endl; else cout<<dp[m]<<endl; }