fork download
copy 
  1. //By Don4ick
  2. //#define _GLIBCXX_DEBUG
  3.  
  4. #include <bits/stdc++.h>
  5.  
  6. typedef long long ll;
  7. typedef long double ld;
  8. typedef unsigned int ui;
  9.  
  10. #define forn(i, n) for (int i = 1; i <= n; i++)
  11. #define pb push_back
  12. #define all(x) x.begin(), x.end()
  13. #define y1 qwer1234
  14.  
  15. const double PI = acos(-1.0);
  16. const int DIR = 4;
  17. const int X[] = {1, 0, -1, 0};
  18. const int Y[] = {0, 1, 0, -1};
  19.  
  20. const int N = (int)2e5 + 228;
  21. const ll INF = (ll)1e18 + 228;
  22.  
  23. using namespace std;
  24.  
  25. int n, a[N], ptr[N << 2], l1[N], r1[N], p[N];
  26. ll dp[N];
  27. vector < pair < ll, ll > > t[N << 2];
  28.  
  29. double cross(pair < ll, ll > x, pair < ll, ll > y)
  30. {
  31. 	return 1.0 * (0.0 + y.second - x.second) / (0.0 + x.first - y.first); 
  32. }
  33.  
  34. void add(vector < pair < ll, ll > > & v, pair < ll, ll > pp)
  35. {
  36. 	while((int)v.size() >= 2 && cross(v[(int)v.size() - 2], v[(int)v.size() - 1]) > cross(v[(int)v.size() - 2], pp))
  37. 		v.pop_back();
  38. 	v.pb(pp);
  39. }
  40.  
  41. void build(int l, int r, int v, int tl, int tr)
  42. {
  43. 	if (l > r || tl > r || tr < l)	
  44. 		return;
  45. 	if (tl >= l && tr <= r)
  46. 	{
  47. 		ptr[v] = 0;
  48. 		t[v].clear();
  49. 		for (int i = tl; i <= tr; i++)
  50. 		{
  51. 			add(t[v], make_pair(-2ll * (i - 1), dp[i - 1] + 1ll * (i - 1) * (i - 1))); 
  52. 		}
  53. 	}
  54. 	if (tl == tr)
  55. 		return;
  56. 	int mid = (tl + tr) >> 1;
  57. 	build(l, r, v << 1, tl, mid);
  58. 	build(l, r, v << 1 | 1, mid + 1, tr);
  59. }
  60.  
  61. ll get(int l, int r, int v, int tl, int tr, int x)
  62. {
  63. 	if (l > r || tl > r || tr < l)
  64. 		return INF;
  65. 	if (tl >= l && tr <= r)
  66. 	{
  67. 		while(ptr[v] < (int)t[v].size() - 1 && 0.0 + x > cross(t[v][ptr[v]], t[v][ptr[v] + 1]))
  68. 			ptr[v]++;
  69. 		if (ptr[v] < (int)t[v].size())
  70. 			return t[v][ptr[v]].first * x + t[v][ptr[v]].second + 1ll * x * x;				 
  71. 		return INF;
  72. 	}
  73. 	int mid = (tl + tr) >> 1;
  74. 	return min(get(l, r, v << 1, tl, mid, x), get(l, r, v << 1 | 1, mid + 1, tr, x));
  75. }
  76.  
  77. void relax(int l, int r, vector < int > v)
  78. {
  79. 	if (v.empty())
  80. 		return;
  81. 	vector < int > v1, v2;
  82. 	vector < pair < ll, ll > > cht;
  83. 	int mid = (l + r) >> 1;
  84. 	for (auto it : v)
  85. 	{
  86. 		if (l1[it] <= l && r1[it] >= r)
  87. 		{
  88. 			add(cht, make_pair(-2ll * (it - 1), dp[it - 1] + 1ll * (it - 1) * (it - 1)));
  89. 		}		
  90. 		else
  91. 		{
  92. 			if (l1[it] <= mid)
  93. 				v1.pb(it);
  94. 			if (r1[it] > mid)
  95. 				v2.pb(it);
  96. 		}
  97. 	}
  98. 	int pp = 0;
  99. 	for (int i = l; i <= r; i++)
  100. 	{
  101. 		while(pp < (int)cht.size() - 1 && cross(cht[pp], cht[pp + 1]) < 0.0 + i)
  102. 			pp++;	
  103. 		if (pp < (int)cht.size())
  104. 			dp[i] = min(dp[i], cht[pp].first * i + cht[pp].second + 1ll * i * i);
  105. 	}
  106. 	if (l == r)
  107. 		return;
  108. 	relax(l, mid, v1);
  109. 	relax(mid + 1, r, v2);	
  110. }
  111.  
  112. void calc(int l, int r)
  113. {
  114. 	if (l == r)
  115. 	{
  116. 		if (a[l] == 1)
  117. 			dp[l] = min(dp[l], dp[l - 1] + 1);
  118. 		return;
  119. 	}
  120. 	int mid = (l + r) >> 1;
  121. 	// p[i] - first upper	
  122. 	calc(l, mid);
  123. 	int mx1 = 0, mx2 = 0, ptr = mid + 1;
  124. 	for (int i = mid + 1; i <= r; i++)
  125. 	{	
  126. 		mx2 = max(mx2, a[i]);
  127. 		while(ptr > l && max(mx1, a[ptr - 1]) <= mx2)
  128. 			mx1 = max(mx1, a[--ptr]);
  129. 		p[i] = ptr;
  130. 	}
  131. 	mx1 = mx2 = 0, ptr = mid;
  132. 	for (int i = mid; i >= l; i--)
  133. 	{
  134. 		mx1 = max(mx1, a[i]);
  135. 		while(ptr < r && max(mx2, a[ptr + 1]) <= mx1)
  136. 			mx2 = max(mx2, a[++ptr]);
  137. 		p[i] = ptr;
  138. 	}
  139. 	build(l, mid, 1, 1, n);
  140. 	mx2 = 0;
  141. 	for (int i = mid + 1; i <= r; i++)
  142. 	{	
  143. 		mx2 = max(mx2, a[i]);
  144. 		dp[i] = min(dp[i], get(p[i], i - mx2 + 1, 1, 1, n, i));
  145. 	}	
  146. 	mx1 = 0;
  147. 	vector < int > v;	
  148. 	for (int i = mid; i >= l; i--)
  149. 	{
  150. 		mx1 = max(mx1, a[i]);
  151. 		l1[i] = i + mx1 - 1;
  152. 		r1[i] = p[i];	
  153. 		v.pb(i);
  154. 	}
  155. 	reverse(all(v));
  156. 	relax(mid + 1, r, v);
  157. 	calc(mid + 1, r);
  158. }                        
  159.  
  160. int main()
  161. {
  162. 	//ios_base::sync_with_stdio(false);
  163. 	//cin.tie(NULL);
  164. 	//cout.tie(NULL);
  165.  
  166. 	//freopen(".in", "r", stdin);
  167. 	//freopen(".out", "w", stdout);
  168.  
  169. 	//~read
  170. 	scanf("%d", &n);
  171. 	forn(i, n)
  172. 		scanf("%d", &a[i]);
  173. 	//~solve
  174. 	fill(dp + 1, dp + n + 1, INF);
  175. 	calc(1, n);
  176. 	cout << dp[n] << endl;
  177.  
  178. 	return 0;
  179. }
Runtime error #stdin #stdout 0.7s 2096112KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pvI7CR
language:
C++ (gcc 8.3)
created:
3 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!