CROC 2016 Qualification : B. Processing Queries

特に何事もなく終了。
http://codeforces.com/contest/644/problem/B

問題

並列処理のできないコンピュータを使い、計N個のクエリを捌く。
各クエリは時刻T[i]に要求が来る。各クエリをこなすにはD[i]の時間がかかる。

クエリが来た時点で、コンピュータがすでに他の処理で稼働中の場合、そのクエリはキューに積まれる。
ただしすでにキューにB個以上のクエリが詰まっている場合、そのクエリは破棄される。
キュー内のクエリは、コンピュータに余裕が出来た時点で先頭から消化される。

各クエリが破棄されるかどうか、されないなら終了時間を答えよ。

解法

Dequeを使い素直にシミュレートしよう。
Dequeには処理中のクエリ及びキューに積まれたクエリの終了時間を格納しておく。

各クエリを順次処理する。
まずDeque内で終了時刻がT[i]以前のものは追い出そう。
それでもまだDeque内のクエリがB個を超えるならクエリを破棄する。
そうでない場合、Deque内の最後のクエリの終了時刻(もしくはDequeが空ならT[i])からそのクエリを開始し、D[i]後に終わると考えて良い。

int N,B;
ll ret[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>B;
	deque<ll> D;
	FOR(i,N) {
		cin>>x>>y;
		while(D.size() && D.front()<=x) D.pop_front();
		
		if(D.size()==0) {
			ret[i]=x+y;
			D.push_back(ret[i]);
		}
		else if(D.size()<=B) {
			ret[i]=D.back()+y;
			D.push_back(ret[i]);
		}
		else {
			ret[i]=-1;
		}
	}
	FOR(i,N) cout<<ret[i]<<" ";
	cout<<endl;
}

まとめ

結局愚直に実装するだけだし、Div2B位？