yukicoder : No.674 n連勤

これライブラリにした方がいいのかな。
https://yukicoder.me/problems/no/674

問題

Q個のクエリが与えられる。
各クエリiは、A[i]日目からB[i]日目が勤務日になることを示す。
各クエリの適用後の時点において、最大連勤日数を求めよ。

解法

色々解法がありそうだが、自分は以下のように解いた。ある意味座標圧縮。

勤務日の開始・終了の境目は(A[i]-1)日目とA[i]日目、またはB[i]日目と(B[i]+1)日目の間である。
よってそれらをsetに放り込もう。
これらはまだ勤務日になっていない日の集合である。

各クエリでは、setからA[i]～B[i]の範囲の数値を取り除く。
クエリによる連勤数の更新の可能性について、lower_bound等でset内におけるB[i]以上の最大値と、A[i]以下の最小値を求めよう。
これはクエリにより勤務日になった日の周辺の非番の日であり、両者の差がA[i]～B[i]を含む連勤日の日数となるので、最大連勤日数の候補となりうる。

ll D;
int Q;
ll A[303030],B[303030];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>D>>Q;
	vector<ll> V;
	V.push_back(-1);
	V.push_back(1LL<<60);
	FOR(i,Q) {
		cin>>A[i]>>B[i];
		V.push_back(A[i]-1);
		V.push_back(A[i]);
		V.push_back(B[i]);
		V.push_back(B[i]+1);
	}
	
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	set<ll> S;
	FOR(i,V.size()) S.insert(V[i]);
	
	ll ret=0;
	FOR(i,Q) {
		while(1) {
			auto it=S.lower_bound(A[i]);
			if(*it>B[i]) break;
			S.erase(*it);
		}
		auto it=S.lower_bound(B[i]);
		ll ed=*it;
		it--;
		ll st=*it;
		ret=max(ret,ed-st);
		cout<<ret-1<<endl;
	}
}

まとめ

出題者はこの4月に社会人になった…ってことはないか。