本番バグが取りきれず数分間に合わなかった…。
http://codeforces.com/contest/589/problem/G
問題
M日間の期間において、各日に確保できる作業時間はT[i]である。
ここで以下N個のクエリに答えよ。
各クエリは2つの値D[i]、R[i]で与えられる。
これは1日の作業時間のうち毎日D[i]は準備でかかり、残りmax(0,T[i]-D[i])だけ作業を行えることを示す。
R[i]の作業を行うのに必要な最低日数を求めよ。
解法
問題を数式で表すと、となる最小のdを求めればよいことになる。
sumが簡単に求められるならこれは二分探索で可能である。
sumを高速に求めることを考える。
面倒なのはsumの中にmaxが入っていることである。
そこで、クエリ及び作業時間をD[i]及びT[i]の順でソートする。
そして2種類のBITを使いd日間の総和を高速に求める。
1つ目のBITはT[i]の総和を求めるものである。
2つ目のBITは、各日が有効か、すなわちT[i]がD[i]を上回るなら1、上回らないなら0を格納したものである。
前者のd日までの総和をF(d)、後者をG(d)とするならば、上記数式の答えはF(d)-G(d)*D[i]となる。
クエリ、作業時間をD,Tの順にソートして1個ずつ処理していき、クエリの場合はF(d)-G(d)*D[i]を求め、作業時間の場合は、以後の処理はその日の作業時間は0と見なしてよいので、両BITのその日の値を0にすると良い。
int N,M; ll T[303030]; ll D[303030],R[303030],ret[303030]; //短縮版 template<class V, int ME> class BIT { public: V bit[1<<ME],val[1<<ME]; V total(int e) {V s=0;e++;while(e) s+=bit[e-1],e-=e&-e; return s;} V add(int e,V v) { val[e++]+=v; while(e<=1<<ME) bit[e-1]+=v,e+=e&-e;} V set(int e,V v) { add(e,v-val[e]);} }; BIT<ll,21> num,tot; vector<int> del[1010100]; vector<int> q[1010100]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>M; FOR(i,M) { cin>>T[i]; num.add(i+1,1); tot.add(i+1,T[i]); del[T[i]].push_back(i); } FOR(i,N) { cin>>D[i]>>R[i]; q[D[i]].push_back(i); } for(int t=0;t<=1000001;t++) { FORR(r,q[t]) { int day=(1<<20)-1; for(j=19;j>=0;j--) if(tot.total(day-(1<<j))-num.total(day-(1<<j))*t>=R[r]) day -= 1<<j; if(day==(1<<20)-1) day=0; ret[r]=day; } FORR(r,del[t]) num.add(r+1,-1),tot.add(r+1,-T[r]); } FOR(i,N) _P("%d ",(int)ret[i]); _P("\n"); }
まとめ
みたいな形の値を高速に求めるテク、今後も使えそうだから頭の片隅に入れておこう。