yukicoder : No.2667 Constrained Permutation

これはどうにか解けた。
https://yukicoder.me/problems/no/2667

問題

N個の整数対(L[i],R[i])が与えられる。
(K+1)～(K+N)のPermutation Pを作ったとき、L[i]≦P[i]≦R[i]を満たせるようなPを作れるKは何通りか。

解法

あり得るKの最小値と最大値を求めよう。
L[i]の小さい順にP[i]の小さい値を割り当てると考えると、Kの最小値が求められる。
同様にR[i]の大きい順にP[i]の大きい値を割り当てると考えると、Kの最大値が求められる。

最後に、実際それらのKの最小値・最大値を満たすPが構築できるか確認し、構築可能であれば、その間の値はすべて条件を満たす。

int N;
pair<int,int> A[202020];

vector<int> add[202020];

int can(int v) {
	int i;
	FOR(i,N) add[i].clear();
	FOR(i,N) {
		int smi;
		if(A[i].first<=v) {
			smi=0;
		}
		else {
			smi=A[i].first-v;
			if(smi>=N) return 0;
		}
		if(A[i].second<v) return 0;
		add[smi].push_back(A[i].second-v);
	}
	multiset<int> A;
	FOR(i,N) {
		FORR(a,add[i]) A.insert(a);
		if(A.size()&&*A.begin()<i) return 0;
		if(A.empty()) return 0;
		A.erase(A.begin());
	}
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i].first>>A[i].second;
	}
	sort(A,A+N);
	
	int kmi=0;
	FOR(i,N) {
		kmi=max(kmi,A[i].first-i);
		swap(A[i].first,A[i].second);
	}
	sort(A,A+N);
	int kma=1<<30;
	FOR(i,N) {
		kma=min(kma,A[i].first-i);
		swap(A[i].first,A[i].second);
	}
	
	if(can(kmi)&&can(kma)) cout<<max(0,kma-kmi+1)<<endl;
	else cout<<0<<endl;
	
}

まとめ

どうにか解けて良かった。