ライブラリの完成度が低くて苦戦。
https://atcoder.jp/contests/wupc2019/tasks/wupc2019_i
問題
通りにN個のラーメン屋ができる。
各ラーメン屋について、位置・開店日・閉店日・おいしさが与えられる。
各ラーメン屋のラーメンの値段は、開店日前日に回転している他のラーメン屋の影響を受け、
- おいしさ
- 開店日前日に回転しているラーメン屋のラーメンの値段+(距離の2乗)
の最小値と一致する。
各ラーメン屋のラーメンの値段を答えよ。
解法
後者の条件よりConvex Hull Trickが使えそうというのは想像がつく。
一方ラーメン屋に閉店日の設定があるので、直線の削除ができないConvex Hull Trickそのままでは扱いにくい。
そこで、日付をキーにし、値に動的Convex Hull Trickを行える構造を載せたSegTreeを作ろう。
ちなみに自分の動的Convex Hull Trickのライブラリはdoubleには使えても整数ではうまく動かなかったので、Li Chao Treeを実装した。
template<typename V> struct LeChaoTree { static const V inf=3LL<<60; const ll range=1<<20; const bool cmptype=false; //true:max false:min struct node { node(V a=0,V b=-inf) : A(a),B(b){ le=ri=NULL;} V val(ll x) { return A*x+B;} V A,B; // Ax+B node *le, *ri; }; node* root; LeChaoTree() { root=new node(0,-inf);} void add(node* n, V a,V b,ll L,ll R) { ll M=(L+R)/2; bool lef=(n->val(L) > a*L+b); bool mid=(n->val(M) > a*M+b); bool ri=(n->val(R) > a*R+b); if(lef&&ri) return; if(!lef&&(!ri || R-L==1)) { n->A=a; n->B=b; return; } if(R-L==1) return; if(!n->ri) n->ri=new node(); if(!n->le) n->le=new node(); add(n->ri,a,b,M,R); add(n->le,a,b,L,M); } void add(V a,V b) { if(!cmptype) a=-a,b=-b; add(root,a,b,0,range); } V query(ll x) { V ret=-inf; node* cur=root; ll L=0, R=range; while(cur) { ret=max(ret,cur->val(x)); ll m=(L+R)/2; if(x<m) cur=cur->le, R=m; else cur=cur->ri, L=m; } if(!cmptype) ret=-ret; return ret; } }; template<class V,int NV> class SegTree_2 { public: vector<V> val; SegTree_2(){ val.resize(NV*2); }; ll getval(int k,ll x) { int e=k+NV; ll ret=3LL<<60; while(e>=1) { ret=min(ret,val[e].query(x)); e>>=1; } return ret; } void update(int x,int y, ll a,ll b,int l=0,int r=NV,int k=1) { if(l>=r) return; if(x<=l && r<=y) { val[k].add(a,b); } else if(l < y && x < r) { update(x,y,a,b,l,(l+r)/2,k*2); update(x,y,a,b,(l+r)/2,r,k*2+1); } } }; SegTree_2<LeChaoTree<ll>,1<<17> st; int N; ll O[101010],C[101010],D[101010],X[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) { cin>>O[i]>>C[i]>>D[i]>>X[i]; if(C[i]==-1) C[i]=101000; X[i]=min(X[i],st.getval(O[i]-1,D[i])+D[i]*D[i]); st.update(O[i],C[i]+1,-2*D[i],X[i]+D[i]*D[i]); cout<<X[i]<<endl; } }
まとめ
Convex Hull Treeのライブラリ、どうも自分で作ってるものの動作に自信がもてない…。