CSAcademy Round #9 : D. Array Removal

最初の４問までは順調だったが、その後手が止まってしまった。
https://csacademy.com/contest/round-9/#task/array-removal

問題

N要素の数列Aがある。
これらのうち、Permutation Pに対してAのP[i]番目の要素を順に利用不可としていく。
１つ利用不可とするたび、利用不可な要素を含まないA中の連続要素の値の総和の最大値を求めよ。

解法

事前にAの累積和を取る。
あとは連続区間の末尾のindexからなるsetと、その連続区間の要素の総和からなるsetを更新すればよい。
後者から区間の総和の最大値がわかるし、前者からP[i]に対しlower_boundを適用することで分割対象となる区間が求められる。

int N;
int A[101010];
ll S[101010];
int st[101010];
set<pair<ll,int>> SS;
set<int> E;

void ins(int s,int e) {
	if(s>e) return;
	st[e]=s;
	E.insert(e);
	SS.insert({S[e+1]-S[s],e});
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>A[i];
		S[i+1]=S[i]+A[i];
	}
	
	ins(0,N-1);
	
	FOR(i,N) {
		cout<<SS.rbegin()->first<<endl;
		cin>>x;
		x--;
		
		y=*E.lower_bound(x);
		SS.erase({S[y+1]-S[st[y]],y});
		E.erase(y);
		
		ins(st[y],x-1);
		ins(x+1,y);
	}
}

まとめ

ここまでは割と簡単。