Codeforces #401 Div2 E. Hanoi Factory

これいつもならDiv2 D位の問題かもね。
http://codeforces.com/contest/777/problem/E

問題

N個のリングがある。それぞれ内径A[i]、外径B[i]、高さH[i]が与えられる。
これらの一部を任意の順番で重ねることを考える。その際以下の条件を満たさなければならない。

• 他の上にあるリングの外径は、直下のリングの外径以下である。
• 他の上にあるリングの外径は、直下のリングの内径より大きい。

重ねたリングの高さを最大化し、その高さを答えよ。

解法

まずA[i],B[i]を合わせて座標圧縮する。

リングを(B[i],A[i])の降順で並べていこう。
B[i]降順で並べると、あとで処理するリングの外径は常に前に処理したリングより小さいので、前者の条件を以後考えなくてよくなる。
また、同じ外径なら内径が小さい方が上に重ねるリングの条件が緩くなるので、内径が大きい順に並べ、一番上に内径が小さいものが来るようにしたいのでA[i]も降順にする。

以下を更新していく考える。
f(r) := 積みかさなったリングの最上段の内径がrの場合の高さの最大値
するとi番のリングを載せたときの高さは H[i] + max(f(0...(B[i]-1)) となるので、fをSegmentTreeで管理していきながらf(r)を更新していくことができる。

int N;
int A[101010],B[101010],H[101010];
vector<int> V;
vector<pair<int,int>> E[202020];

template<class V,int NV> class SegTree_1 {
public:
	vector<V> val;
	static V const def=-1LL<<40;
	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<ll,1<<20> st;
ll TH[202020];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	V.push_back(0);
	FOR(i,N) {
		cin>>A[i]>>B[i]>>H[i];
		V.push_back(A[i]);
		V.push_back(B[i]);
	}
	FOR(i,2*N+2) TH[i]=-1LL<<40;
	TH[0]=0;
	st.update(0,0);
	sort(ALL(V));
	V.erase(unique(ALL(V)),V.end());
	FOR(i,N) {
		A[i]=lower_bound(ALL(V),A[i])-V.begin();
		B[i]=lower_bound(ALL(V),B[i])-V.begin();
		E[B[i]].push_back({A[i],i});
	}
	ll ma=0;
	for(i=200010;i>=0;i--) {
		sort(ALL(E[i]));
		reverse(ALL(E[i]));
		FORR(e,E[i]) {
			x=e.second;
			ll v=max(0LL,st.getval(0,B[x]))+H[x];
			if(v>TH[A[x]]) {
				ma=max(ma,v);
				TH[A[x]]=v;
				st.update(A[x],v);
			}
		}
	}
	cout<<ma<<endl;
	
	
}

まとめ

こういう問題は嫌いじゃない。