Submission #2544580

---

Source Code Expand

#include <bits/stdc++.h>
#define range(i, a, b) for(int i = (a); i < (b); i++)
#define rep(i, a) range(i, 0, a)
using namespace std;

int n;
const int INF = 1e9;

int solve (map <int, int> &line) {
	vector <int> dp(n, INF);
	for (auto &i : line) {
		*lower_bound(dp.begin(), dp.end(), i.second) = i.second;
	}
	return lower_bound(dp.begin(), dp.end(), INF) - dp.begin();
}

int main() {
	cin >> n;
	map <int, int> xy, yx;
	rep (i, n) {
		int h, w;
		cin >> w >> h;
		xy[w] = h;
		yx[h] = w;
	}

	cout << max(solve(xy), solve(yx)) << endl;

	return 0;
}

Submission Info

Judge Result