2015-2016 ACM-ICPC NEERC : G. Hiring

本番バグが取りきれず数分間に合わなかった…。
http://codeforces.com/contest/589/problem/G

問題

M日間の期間において、各日に確保できる作業時間はT[i]である。
ここで以下N個のクエリに答えよ。

各クエリは2つの値D[i]、R[i]で与えられる。
これは１日の作業時間のうち毎日D[i]は準備でかかり、残りmax(0,T[i]-D[i])だけ作業を行えることを示す。
R[i]の作業を行うのに必要な最低日数を求めよ。

解法

問題を数式で表すと、となる最小のdを求めればよいことになる。
sumが簡単に求められるならこれは二分探索で可能である。

sumを高速に求めることを考える。
面倒なのはsumの中にmaxが入っていることである。

そこで、クエリ及び作業時間をD[i]及びT[i]の順でソートする。
そして2種類のBITを使いd日間の総和を高速に求める。
１つ目のBITはT[i]の総和を求めるものである。
２つ目のBITは、各日が有効か、すなわちT[i]がD[i]を上回るなら1、上回らないなら0を格納したものである。
前者のd日までの総和をF(d)、後者をG(d)とするならば、上記数式の答えはF(d)-G(d)*D[i]となる。

クエリ、作業時間をD,Tの順にソートして１個ずつ処理していき、クエリの場合は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");
}

まとめ

みたいな形の値を高速に求めるテク、今後も使えそうだから頭の片隅に入れておこう。