AtCoder ARC #165 : B - Sliding Window Sort 2

最近AtCoder系振るわなさすぎるな…。
https://atcoder.jp/contests/arc165/tasks/arc165_b

問題

整数列Pが与えられる。
このうち長さKの連続部分列を1つ選び、昇順にソートすることを考える。
その後のPのうち、辞書順最大なものを求めよ。

解法

ソートによる値が小さくなる添え字の位置が一番後ろとなるものを選べばよい。
ソートする範囲のウインドウをずらしながら、各要素につきソートにより値が小さくなるようなものの集合を求めよう。
各ウインドウに対し、値が小さくなる要素の最小値が最大となる箇所を求め、そこでソートすればよい。

int N,K;
int P[202020];


int R[202020];
int nex[202020];
set<int> S;
set<int> CC;
vector<int> ev[405020];
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>P[i];
		R[P[i]-1]=i;
	}
	S.insert(404040);
	FOR(i,N) {
		nex[i]=*S.lower_bound(R[i]);
		ev[nex[i]].push_back(R[i]);
		S.insert(R[i]);
	}
	
	int cand=0;
	int mi=-1;
	CC.insert(404040);
	FOR(i,K-1) FORR(e,ev[i]) CC.insert(e);
	FOR(i,N) if(i+K<=N) {
		FORR(e,ev[i+K-1]) CC.insert(e);
		while(CC.size()&&*CC.begin()<i) CC.erase(CC.begin());
		x=*CC.begin();
		if(x>mi) {
			mi=x;
			cand=i;
		}
	}
	sort(P+cand,P+cand+K);
	FOR(i,N) cout<<P[i]<<" ";
	cout<<endl;
	
		
}

まとめ

ちょっと手間取りすぎ。