AtCoder ARC #165 : B - Sliding Window Sort 2

出来がいまいちだった回。
https://atcoder.jp/contests/arc165/tasks/arc165_b

問題

1～Nの順列Pと整数Kを与えられる。
Pのうち、連続するK要素を1回だけ行うとき、得られるKの辞書順最大値を求めよ。

解法

処理を行うと、辞書順で大きくなることはない。
そこで、各位置で処理を行ったとき、値が初めて書き換わるindexがどこになるかを考える。
書き換わるindexが最大となる位置のうち、最も手前の位置で処理するのが良い。

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;
	
		
}

まとめ

本番結構苦戦してるな。