fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #define ll long long
  5. using namespace std;
  6. const int MX = 3e5+10;
  7. ll MOD = 1000000007, INF = -1;
  8. ll a[MX], len[2][MX], cnt[2][MX], sum[2][MX];
  9. ll t[2][2][4*MX], idx[MX];
  10.  
  11. //a[0][i] ending on down stroke
  12. //a[1][i] ending on up stroke
  13. //T = 0 min
  14. //T = 1 max
  15.  
  16. int ask(int T, int tp, int v, int tl, int tr, int l, int r) {
  17. 	if (l > r)
  18. 		return 0;
  19. 	if (l == tl && r == tr)
  20. 		return t[T][tp][v];
  21. 	int tm = (tl + tr) / 2;
  22. 	int L = ask(T, tp, v*2, tl, tm, l, min(r,tm)), R = ask(T, tp, v*2+1, tm+1, tr, max(l,tm+1), r);
  23. 	if (len[tp][L] == len[tp][R]) {
  24. 		if (T == 0) {
  25. 			return min(L, R);
  26. 		}
  27. 		else return max(L, R);
  28. 	}
  29. 	else if (len[tp][L] > len[tp][R]) {
  30. 		return L;
  31. 	}
  32. 	else {
  33. 		return R;
  34. 	}
  35. }
  36.  
  37. void update(int T, int tp, int v, int tl, int tr, int pos) {
  38. 	if (tl == tr)
  39. 		t[T][tp][v] = idx[tl];
  40. 	else {
  41. 		int tm = (tl + tr) / 2;
  42. 		if (pos <= tm)
  43. 			update(T, tp, v*2, tl, tm, pos);
  44. 		else
  45. 			update(T, tp, v*2+1, tm+1, tr, pos);
  46. 		int L = t[T][tp][v*2], R = t[T][tp][v*2+1];
  47. 		if (len[tp][L] == len[tp][R]) {
  48. 			if (T == 0) {
  49. 				t[T][tp][v] = min(L, R);
  50. 			}
  51. 			else {
  52. 				t[T][tp][v] = max(L, R);
  53. 			}
  54. 		}
  55. 		else if (len[tp][L] > len[tp][R]) {
  56. 			t[T][tp][v] = L;
  57. 		}
  58. 		else {
  59. 			t[T][tp][v] = R;
  60. 		}
  61. 	}
  62. }
  63.  
  64. int main() {
  65. 	int n; cin >> n;
  66. 	for (int i = 1; i <= n; i++) {
  67. 		cin >> a[i];
  68. 		idx[a[i]] = i;
  69. 	}
  70. 	int mxlen = 0;
  71. 	sum[0][0] = sum[1][0] = 1;
  72. 	for (int i = 1; i <= n; i++) {
  73. 		for (int j = 0; j <= 1; j++) {
  74. 			int best_lo, best_hi, best;
  75. 			if (j == 1) {
  76. 				best_lo = ask(0, 0, 1, 1, n, 1, a[i]-1);
  77. 				best_hi = ask(1, 0, 1, 1, n, 1, a[i]-1);
  78. 				best = len[0][best_lo]+1;
  79. 			}
  80. 			else {
  81. 				best_lo = ask(0, 1, 1, 1, n, a[i]+1, n);
  82. 				best_hi = ask(1, 1, 1, 1, n, a[i]+1, n);
  83. 				best = len[1][best_lo]+1;
  84. 			}
  85. 			len[j][i] = best;
  86. 			update(0, j, 1, 1, n, a[i]);
  87. 			update(1, j, 1, 1, n, a[i]);
  88. 			mxlen = max(mxlen, best);
  89. 			cnt[j][i] = (sum[1-j][best_hi]-sum[1-j][best_lo-1]+MOD)%MOD;
  90. 			sum[j][i] = (sum[j][i-1]+cnt[j][i])%MOD;
  91. 		}
  92. 	}
  93. 	ll ans = 0;
  94. 	for (int i = 1; i <= n; i++) {
  95. 		if (len[0][i] == mxlen) {
  96. 			ans = (ans+cnt[0][i])%MOD;
  97. 		}
  98. 		if (len[1][i] == mxlen) {
  99. 			ans = (ans+cnt[1][i])%MOD;
  100. 		}
  101. 		//cout << i << " " << len[0][i] << " " << len[1][i] << '\n';
  102. 	}
  103. 	cout << mxlen << " " << ans << '\n';
  104. 	return 0;
  105. }
Runtime error #stdin #stdout 0s 59728KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/km15rW
language:
C++14 (gcc 8.3)
created:
7 years 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!