fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3. using namespace std;
  4. const int N = 2e5 + 5;
  5. int memo[N];
  6. vector <int> a[N];
  7.  
  8. bool ch(int d1, int h1, int d2, int h2) {
  9. 	return d1 < d2 && h1 > h2;
  10. }
  11.  
  12. int f(int n) {
  13. 	if (memo[n] != -1) return memo[n];
  14. 	int res = 1;
  15. 	for (int x : a[n]) {
  16. 		res = max(res, f(x) + 1);
  17. 	}
  18. 	return res;
  19. }
  20.  
  21. signed main() {
  22. 	ios_base::sync_with_stdio(0);
  23. 	cin.tie(0);
  24. 	int n;
  25. 	cin >> n;
  26. 	int d[n], h[n];
  27. 	for (int i = 0; i < n; ++i) cin >> d[i] >> h[i];
  28. 	for (int i = 0; i < n; ++i) {
  29. 		for (int j = 0; j < n; ++j) {
  30. 			if (ch(d[j], h[j], d[i], h[i])) a[i].push_back(j);
  31. 		}
  32. 	}
  33. 	memset(memo, -1, sizeof(memo));
  34. 	for (int i = 0; i < n; ++i) cout << f(i) << '\n';
  35. 	return 0;
  36. }
Success #stdin #stdout 0.01s 9740KB
comments (?)
stdin
copy 
3
1 2
2 1
1 3
stdout
copy 
1
2
1
https://ideone.com/KnaKux
language:
C++ (gcc 8.3)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!