Codeforces #857 : Div1 C. Music Festival

これは割とすんなり。
https://codeforces.com/contest/1801/problem/C

問題

数列Xのcoolnessとは、X[i]がmax(X[0...(i-1)])より大きいようなiの個数とする。
N個の数列A[i]が与えられる。これらの数列を任意の順で連結できるとき、coolnessの最大値を求めよ。

解法

まず各数列についてcoolnessの増加に寄与しない要素は削除しておく。
数列を連結する際、最大値が大きな数列を先に持ってくると、最大値が小さな数列がcoolnessに寄与しないので損である。

f(n,k) := n個目までの数列を考えたとき、最大値がkであるときのcoolnessの最大値
を考えると、f(n,*)を区間最大値を取れるSegTreeで保持しf(n+1,*)を順次更新していけばよい。

int T,N;
vector<int> A[202020];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=0;
	V comp(V l,V r){ return max(l,r);};
	
	SegTree_1(){val=vector<V>(NV*2,def);};
	V getval(int x,int y,int l=0,int r=NV,int k=1) { // x<=i<y
		if(r<=x || y<=l) return def;
		if(x<=l && r<=y) return val[k];
		return comp(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
	}
	void update(int entry, V v) {
		entry += NV;
		val[entry]=v;
		while(entry>1) entry>>=1, val[entry]=comp(val[entry*2],val[entry*2+1]);
	}
};
SegTree_1<int,1<<20> st;
void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		vector<pair<int,int>> cand;
		FOR(i,N) {
			cin>>x;
			A[i].clear();
			FOR(j,x) {
				cin>>y;
				if(A[i].empty()||y>A[i].back()) A[i].push_back(y);
			}
			cand.push_back({A[i].back(),i});
		}
		sort(ALL(cand));
		int ret=0;
		FORR2(a,i,cand) {
			int ma=st.getval(0,a+1);
			FOR(j,A[i].size()) {
				ma=max(ma,st.getval(0,A[i][j])+(int)A[i].size()-j);
			}
			ret=max(ret,ma);
			st.update(a,ma);
		}
		
		FOR(i,N) FORR(v,A[i]) st.update(v,0);
		cout<<ret<<endl;
	}
}

まとめ

Div1 Cの割に簡単だと思ったら、1250ptだった。