fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define fi first
  5. #define se second
  6. #define ii pair<int, int>
  7.  
  8. const int N = 1e6 + 7;
  9. int n, m, a[N], BIT[N], d[2][N];
  10. ii nef[N];
  11.  
  12. void updateUP(int x, int val) {
  13. 	while (x <= m) {
  14. 		BIT[x] = max(BIT[x], val);
  15. 		x += x & -x;
  16. 	}
  17. }
  18.  
  19. void updateDOWN(int x, int val) {
  20. 	while (x > 0) {
  21. 		BIT[x] = max(BIT[x], val);
  22. 		x -= x & -x;
  23. 	}
  24. }
  25.  
  26. int getUP(int x) {
  27. 	int res = 0;
  28. 	while (x <= m) {
  29. 		res = max(res, BIT[x]);
  30. 		x += x & -x;
  31. 	}
  32. 	return res;
  33. }
  34.  
  35. int getDOWN(int x) {
  36. 	int res = 0;
  37. 	while (x > 0) {
  38. 		res = max(res, BIT[x]);
  39. 		x -= x & -x;
  40. 	}
  41. 	return res;
  42. }
  43.  
  44. void nen() {
  45. 	sort(nef + 1, nef + n + 1);
  46. 	m = 0;
  47. 	for (int i = 1; i <= n; ++i) {
  48. 		if (nef[i].fi != nef[i - 1].fi) ++m;
  49. 		a[nef[i].se] = m;
  50. 	}
  51. }
  52.  
  53. void reset() {
  54. 	memset(BIT, 0, sizeof(int) * (m + 2));
  55. 	for (int i = 1; i <= n; ++i)
  56. 		d[0][i] = d[1][i], d[1][i] = 0;
  57. }
  58.  
  59. void inp() {
  60. 	cin >> n;
  61. 	for (int i = 1; i <= n; ++i) {
  62. 		cin >> a[i];
  63. 		nef[i] = {a[i], i};
  64. 	}
  65. 	nen();
  66. }
  67.  
  68. void solve() {
  69. 	for (int i = 1; i <= n; ++i) {
  70. 		d[1][i] = getDOWN(a[i] - 1) + 1;
  71. 		updateUP(a[i], d[1][i]);
  72. 	}
  73. 	reset();
  74.  
  75. 	for (int i = 1; i <= n; ++i) {
  76. 		d[1][i] = getUP(a[i] + 1) + 1;
  77. 		if (d[1][i] > 2) updateDOWN(a[i], d[1][i]);
  78. 		if (d[0][i] > 1) updateDOWN(a[i], d[0][i]);
  79. 	}
  80. 	reset();
  81.  
  82. 	for (int i = 1; i <= n; ++i) {
  83. 		d[1][i] = getDOWN(a[i] - 1) + 1;
  84. 		if (d[1][i] > 3) updateUP(a[i], d[1][i]);
  85. 		if (d[0][i] > 2) updateUP(a[i], d[0][i]);
  86. 	}
  87. 	reset();
  88.  
  89. 	for (int i = 1; i <= n; ++i) {
  90. 		d[1][i] = getUP(a[i] + 1) + 1;
  91. 		if (d[1][i] > 4) updateDOWN(a[i], d[1][i]);
  92. 		if (d[0][i] > 3) updateDOWN(a[i], d[0][i]);
  93. 	}
  94.  
  95. 	int ans = 0;
  96. 	for (int i = 1; i <= n; ++i)
  97. 		ans = max(ans, d[1][i]);
  98. 	cout << ans;
  99. }
  100.  
  101. int main(){
  102. 	faster;
  103. 	inp();
  104. 	solve();
  105. 	return 0;
  106. }
  107. // cnlk
  108.  
Success #stdin #stdout 0s 5688KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/xPvPMb
language:
C++14 (gcc 8.3)
created:
3 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!