Codeforces #550: Div3. G. Two Merged Sequences

ぼちぼち難しめのDiv3ボス問が出てきた。
https://codeforces.com/contest/1144/problem/G

問題

数列が与えられる。
この数列を１つの増加列と１つの減少列を混ぜたものとして構築可能か。
可能なら元の２つの列の例を示せ。

解法

以下を先頭から見ていく。
dp0(n) := n要素目を増加列に入れたとき、減少列の末尾の値の最大値
dp1(n) := n要素目を減少列に入れたとき、増加列の末尾の値の最小値

各要素を減少列か増加列に入れられるか判定していけばよい。

int N;
int A[202020];

int LIS[202020];
int LDS[202020];
int from[202020][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	MINUS(from);
	
	FOR(i,N) {
		cin>>A[i];
		if(i==0) {
			LIS[i]=200001;
			LDS[i]=-1;
			from[i][0]=from[i][1]=0;
		}
		else {
			LIS[i]=-1;
			LDS[i]=200001;
			if(from[i-1][0]>=0) {
				// {A[i-1],LIS[i-1]}
				if(A[i]>A[i-1]) {
					LIS[i]=LIS[i-1];
					from[i][0]=0;
				}
				if(A[i]<LIS[i-1]) {
					LDS[i]=A[i-1];
					from[i][1]=0;
				}
			}
			if(from[i-1][1]>=0) {
				// {LDS[i-1],A[i-1]};
				if(A[i]>LDS[i-1] && A[i-1]>LIS[i]) {
					LIS[i]=A[i-1];
					from[i][0]=1;
				}
				if(A[i]<A[i-1] && LDS[i-1]<LDS[i]) {
					LDS[i]=LDS[i-1];
					from[i][1]=1;
				}
			}
		}
	}
	
	FOR(i,2) {
		if(from[N-1][i]>=0) {
			cout<<"YES"<<endl;
			
			vector<int> V;
			int cur=i;
			for(j=N-1;j>=0;j--) {
				V.push_back(cur);
				cur=from[j][cur];
			}
			
			
			reverse(ALL(V));
			FORR(v,V) cout<<v<<" ";
			cout<<endl;
			return;
		}
	}
	cout<<"NO"<<endl;
	
}

まとめ

Div3ボス問としてはちょうどよい難易度？