fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const ll LINF = 1e18;  
  9.  
  10. const int N = 3e4 + 5;  
  11.  
  12. int n;  
  13. ll a[N]; 
  14. int dp[N]; // dp[i] = độ dài dãy con tăng dài nhất kết thúc tại i 
  15.  
  16. void compress(ll a[]) {
  17. 	vector<ll> vals;  
  18. 	for (int i = 1; i <= n; i++) vals.push_back(a[i]);  
  19.  
  20. 	sort(vals.begin(), vals.end());   
  21. 	vals.resize(unique(vals.begin(), vals.end()) - vals.begin());
  22.  
  23. 	for (int i = 1; i <= n; i++) {
  24. 		a[i] = lower_bound(vals.begin(), vals.end(), a[i]) - vals.begin(); 
  25. 		a[i] = a[i] + 1;  
  26. 	}
  27. }
  28.  
  29. int ft[N]; 
  30.  
  31. int getMax(int i) {
  32. 	int ans = 0;   
  33. 	for (; i > 0; i -= i & (-i)) ans = max(ans, ft[i]); 
  34. 	return ans; 
  35. }
  36.  
  37. void update(int i, int val) {
  38. 	for (; i <= n; i += i & (-i)) ft[i] = max(ft[i], val); 
  39. }
  40.  
  41. int main() {
  42. 	ios::sync_with_stdio(0); cin.tie(0);  	
  43. 	cin >> n; 
  44. 	for (int i = 1; i <= n; i++) cin >> a[i];
  45.  
  46. 	// for (int i = 1; i <= n; i++) {
  47. 	// 	dp[i] = 1;   
  48. 	// 	for (int j = 1; j < i; j++) {
  49. 	// 		// max của tất cả các dp[j] ở đằng trước sao cho a[j] thuộc đoạn [1, a[i] - 1]
  50. 	// 		if (a[j] < a[i]) dp[i] = max(dp[i], dp[j] + 1); 
  51. 	// 	}
  52. 	// } // O(n^2)
  53.  
  54. 	compress(a);  
  55.  
  56. 	for (int i = 1; i <= n; i++) {
  57. 		dp[i] = 1;   
  58. 		dp[i] = getMax(a[i] - 1) + 1; 
  59. 		update(a[i], dp[i]); 
  60. 	} // O(n * log2(n))
  61.  
  62. 	int ans = 0;  
  63. 	for (int i = 1; i <= n; i++) ans = max(ans, dp[i]); 
  64.  
  65. 	cout << ans << '\n'; 
  66. }
  67.  
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
5
2 1 4 3 5
stdout
copy 
3
https://ideone.com/WVXktx
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

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!