ABC038 D - プレゼント

D - プレゼント

概要

N項の数列HとWが与えられ、N個の箱の縦の長さと横の長さを表す。箱iと箱jはHi < Hj かつ Wi < Wjであるとき、iをjの中に入れることが出来る。またこの条件を満たした上で複数の箱を同時に入れることもできる。最も外側の箱を含め、最大いくつの箱を入れ子にすることができるか。

制約

1 ≦ N ≦ 10^5
1 ≦ H, W ≦ 10^5

方針

Hが全て異なる場合は、H・WのペアについてHを昇順に並べた後、WのLISの長さが答え。
Hに同じものが含まれる場合は、一見このやり方ではできないように見えるが、実はWを降順にするとうまくいく。

別解として、区間最大を管理するセグメント木を用いても解くことができる。（要確認）

解答

Submission #5828534 - AtCoder Beginner Contest 038

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
const int max_n = 100005;
 
int N;
int a[max_n];
int l[max_n];
// l[i] : 長さiの増加部分列の最後の要素の最小値
 
int lis(){
	l[0] = a[0];
	int len = 1;
 
	for(int i = 1; i < N; i++){
		if(l[len-1] < a[i]){
			l[len++] = a[i];
		}else{
			// lの中でa[i]以上となる最初の場所を探し、それをa[i]とする
			*lower_bound(l, l + len, a[i]) = a[i];
		}
	}
 
	return len;
}
 
bool comp(pii lhs, pii rhs){
	if(lhs.first == rhs.first){
		return lhs.second > rhs.second;
	}
 
	return lhs.first < rhs.first;
}
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> N;
 
	vector<pii> v(N);
	rep(i, N){
		cin >> v[i].first >> v[i].second;
	}
 
	sort(v.begin(), v.end(), comp);
 
	// rep(i, N){
	// 	cout << v[i].first << "," << v[i].second << endl;
	// }
 
	rep(i, N) {
		a[i] = v[i].second;
	}
 
	cout << lis() << endl;
}