HackerRank University CodeSprint 5 : G. Sword profit

これ90pt…？
https://www.hackerrank.com/contests/university-codesprint-5/challenges/sword-profit

問題

N個の店が順に並んでいる。
各店では剣を売買できる。
i番の店では質Q[i]の剣を購入できる。その際、その店でK本目の剣を買うにはA[i]+K*B[i]の値段がかかる。
剣を持ち歩くと、隣の店に行くたびに質がD[i]低下する。
各店は、任意の剣を買い取ることができる。その際、質Qの剣があれば価格Q-R[i]で買い取る。

無限に大きなお金を持った人が、1番から順に店を訪問することを考える。
うまく剣の売買をしたとき、差益の最大額はいくらか。

解法

剣の売却額は購入額に依存しないので、各店で買った剣をどこで売るのがベストかは一意に求まる。
i番の店で買った剣をj番の店で買った場合の売却益は、Q[i] - (A[i]+K*B[i]) - R[j] - (j-i)*D[i]となる。
よってD[i]*j + R[j]が最小となるjで売却するのが良い。これはConvex Hull Trickを用いれば求まる。

各店に対し売る店が決まったら売却益が正になる範囲で買いこめばよい。

template<typename V> struct ConvexHull {
	deque<pair<V,V>> Q;
	V calc(pair<V,V> p, V x) {
		return p.first*x+p.second;
	}
	int dodo(pair<V,V> A,pair<V,V> B, pair<V,V> C) { // max or min
		return ((A.second-C.second)*(B.first-A.first)<=(A.second-B.second)*(C.first-A.first));
	}
	void add(V a, V b) { // add ax+b
		Q.push_back({a,b});
		int v;
		while((v=Q.size())>=3 && dodo(Q[v-3],Q[v-2],Q[v-1]))
			Q[v-2]=Q[v-1], Q.pop_back();
	}
	V query(V x) {
		int L=-1,R=Q.size()-1;
		while(R-L>1) {
			int M=(L+R)/2;
			(((calc(Q[M],x)>=calc(Q[M+1],x)))?L:R)=M;
		}
		return calc(Q[R],x);
	}
};

ConvexHull<ll> ch;
int N;
ll Q[303030],A[303030],B[303030],R[303030],D[303030];
ll mo=1000000007;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>Q[i]>>A[i]>>B[i]>>R[i]>>D[i];
	ll ret=0;
	for(i=N-1;i>=0;i--) {
		ch.add(i,R[i]);
		Q[i]-=A[i]+ch.query(D[i])-(D[i]*i)+B[i];
		if(Q[i]>0) {
			__int128_t q=Q[i]%mo;
			__int128_t num=(Q[i]/B[i]+1)%mo;
			ret+=(q*num-num*(num-1)/2*B[i])%mo;
		}
	}
	cout<<(ret%mo+mo)%mo<<endl;
	
	
	
}

まとめ

挿入中任意のCHTが要るわけでもないし、なぜこれ90ptなんだ…
と思ってたら、CHTのライブラリがバグっていて手間取った。