fork download 
  1. #pragma GCC target ("avx2")
  2. #pragma GCC optimization ("O3")
  3. #pragma GCC optimization ("unroll-loops")
  4. #include <algorithm>
  5. #include <assert.h>
  6. #include <bitset>
  7. #include <cfloat>
  8. #include <complex>
  9. #include <deque>
  10. #include <fstream>
  11. #include <functional>
  12. #include <iomanip>
  13. #include <iostream>
  14. #include <limits.h>
  15. #include <list>
  16. #include <map>
  17. #include <math.h>
  18. #include <queue>
  19. #include <random>
  20. #include <set>
  21. #include <stack>
  22. #include <string>
  23. #include <string.h>
  24. #include <time.h>
  25. #include <unordered_map>
  26. #include <unordered_set>
  27. #include <vector>
  28. #define rep(i,n) for(int i=0;i<n;i++)
  29. #define REP(i,n) for(int i=1;i<=n;i++)
  30. #define ll long long
  31. #define eps LDBL_EPSILON
  32. #define mod (int)1000000007
  33. #define INF INT_MAX/10
  34. #define P pair<int,int>
  35. #define prique(T) priority_queue<T,vector<T>,greater<T>>
  36. #define all(V) V.begin(),V.end()
  37. using namespace std;
  38.  
  39. class ConvexHullTrick {
  40. 	bool minOrMax, lineMonotone;
  41. 	class Line {
  42. 	public:
  43. 		int a, b;
  44. 		bool isquery;
  45. 		mutable std::function<const Line * ()> getSuc;
  46. 		bool operator<(const Line& x) const {
  47. 			if (isquery) {
  48. 				const Line* suc = next(this);
  49. 				if (suc == nullptr) return true;
  50. 				return (suc->a - x.a) * a + suc->b - x.b > 0;
  51. 			}
  52. 			if (x.isquery) {
  53. 				const Line* suc = next(this);
  54. 				if (suc == nullptr) return false;
  55. 				return (suc->a - a) * x.a + suc->b - b < 0;
  56. 			}
  57. 			return a < x.a;
  58. 		}
  59. 	};
  60. 	bool isbad(const set<Line>::iterator x) {
  61. 		if (x == st.begin() || next(x) == st.end())return false;
  62. 		auto pre = prev(x), nex = next(x);
  63. 		if (((*x).b - (*pre).b) * ((*nex).a - (*x).a) >= ((*nex).b - (*x).b) * ((*x).a - (*pre).a))return true;
  64. 		return false;
  65. 	}
  66. 	bool isbad(const vector<Line>::iterator x) {
  67. 		if (x == vec.begin() || next(x) == vec.end())return false;
  68. 		auto pre = prev(x), nex = next(x);
  69. 		if (((*x).b - (*pre).b) * ((*nex).a - (*x).a) >= ((*nex).b - (*x).b) * ((*x).a - (*pre).a))return true;
  70. 		return false;
  71. 	}
  72. 	set<Line> st;
  73. 	vector<Line> vec;
  74. public:
  75. 	ConvexHullTrick(bool minormax = false, bool lineMonotone = false) :minOrMax(minormax), lineMonotone(lineMonotone) {}
  76. 	void addLine(int a, int b) {
  77. 		if (minOrMax) {
  78. 			a = -a; b = -b;
  79. 		}
  80. 		if (!lineMonotone) {
  81. 			auto pos = st.lower_bound({ a,-INF,false });
  82. 			if (pos != st.end()) {
  83. 				if ((*pos).a == a) {
  84. 					if ((*pos).b <= b)return;
  85. 					st.erase(pos);
  86. 				}
  87. 			}
  88. 			auto ite = st.insert({ a,b,false }).first;
  89. 			ite->getSuc = [=] {return next(ite) == st.end() ? nullptr : &*next(ite); };
  90. 			if (isbad(ite)) {
  91. 				st.erase(ite);
  92. 				return;
  93. 			}
  94. 			while (next(ite) != st.end() && isbad(next(ite)))st.erase(next(ite));
  95. 			while (ite != st.begin() && isbad(prev(ite)))st.erase(prev(ite));
  96. 		}
  97. 		else {
  98. 			if (!vec.empty()) {
  99. 				if (vec.back().a > a) {
  100. 					cerr << "Line additions are not monotone" << endl;
  101. 					exit(1);
  102. 				}
  103. 				if (vec.back().a == a) {
  104. 					if (vec.back().b <= b)return;
  105. 					vec.pop_back();
  106. 				}
  107. 			}
  108. 			vec.push_back({ a,b,false });
  109. 			auto ite = --vec.end();
  110. 			int index = vec.size() - 1;
  111. 			ite->getSuc = [this, index] {cout << vec.size() << endl; return index == vec.size() - 1 ? nullptr : &*(vec.begin() + index + 1); };
  112. 			while (ite != vec.begin() && isbad(prev(ite))) {
  113. 				*prev(ite) = vec.back();
  114. 				vec.pop_back();
  115. 				ite = --vec.end();
  116. 			}
  117. 		}
  118. 	}
  119. 	int query(int x) {
  120. 		if (!lineMonotone) {
  121. 			auto l = *st.lower_bound(Line{ x, 0,true });
  122. 			if (!minOrMax)return l.a * x + l.b;
  123. 			else return -l.a * x - l.b;
  124. 		}
  125. 		else {
  126. 			auto l = *lower_bound(vec.begin(), vec.end() - 1, Line({ x,0,true }));
  127. 			if (!minOrMax)return l.a * x + l.b;
  128. 			else return -l.a * x - l.b;
  129. 		}
  130. 	}
  131. };
  132.  
  133. //COLOCON2018Final-C
  134. int n, a[200010];
  135. signed main() {
  136. 	ConvexHullTrick cht(false, true);
  137. 	cin >> n;
  138. 	rep(i, n)cin >> a[i];
  139. 	for (int i = n - 1; i >= 0; i--)cht.addLine(-2 * i, a[i] + i * i);
  140. 	rep(i, n) {
  141. 		cout << cht.query(i) + i * i << endl;
  142. 	}
  143. 	return 0;
  144. }
Success #stdin #stdout 0s 4500KB
comments (?)
stdin 
12
10 14 64 20 24 12 12 21 30 44 29 2
stdout 
10
11
14
16
13
12
12
13
11
6
3
2
https://ideone.com/sNcvvu
language:
C++14 (gcc 8.3)
created:
5 years 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!