fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <boost/multiprecision/cpp_int.hpp>
  3. #include <boost/multiprecision/cpp_dec_float.hpp>
  4. using namespace std;
  5.  
  6. /***** type *****/
  7. using ll = long long;
  8. using ld = long double;
  9. using ml = boost::multiprecision::cpp_int;
  10. using md = boost::multiprecision::cpp_dec_float_100;
  11. using pll = pair<long, long>;
  12. template <class T> using vt = vector<T>;
  13. template <class T> using vvt = vector<vector<T>>;
  14. template <class T> using vvvt = vector<vector<vector<T>>>;
  15. template <class T> using uset = unordered_set<T>;
  16. template <class T1, class T2> using umap = unordered_map<T1, T2>;
  17.  
  18. /***** define *****/
  19. #define all(c) (c).begin(), (c).end()            // begin to end
  20. #define coutld cout << fixed << setprecision(10) // cout long double
  21. #define rep(i, b, e) for (ll i = b; i < e; i++)  // repeat
  22. #define repr(i, b, e) for (ll i = b; e < i; i--) // repeat reverse
  23. #define pair NyaaPair                            // nyaa pair
  24. #define first f                                  // pair::first
  25. #define second s                                 // pair::second
  26. /***** const value *****/
  27. #define llong_max 9223372036854775807            // 9 * 10^18
  28. #define ldbl_max 1.79769e+308                    // 1.7 * 10^308
  29. #define pi 3.1415926535897932                    // 3.14 ...
  30. #define loop_end 9223372036854775806             // LLONG_MAX-1
  31. /***** for each macro *****/
  32. #define fori(i, ...) if(ll i = -1) for(__VA_ARGS__) if(i++, true)
  33. #define each(i, e, c) fori(i, auto& e: c)
  34. #define forir(i, v, ...) if(ll i=(ll)v.size())for(__VA_ARGS__)if(i--,true)
  35. #define eachr(i, e, c) forir(i, auto e = c.rbegin(); e != c.rend(); ++e)
  36.  
  37. /***** lambda *****/
  38. auto Count = [] // long long count value
  39. (auto b, auto e, auto x) { return (ll)count(b, e, x); };
  40. auto CtoL = [] // char to number
  41. (auto c) { return (ll)(c - '0'); };
  42. auto CeilD = [] // long double ceiling div
  43. (auto a, auto b) { return ceil((ld)a / (ld)b); };
  44. auto Fix = [] // fix value
  45. (auto b, auto e, auto fix)
  46. { for (auto it = b; it != e; ++it) *it += fix; };
  47. auto LtoC = [] // number to char
  48. (auto n) { return (char)('0' + n); };
  49. auto Pow = [] // long long pow
  50. (auto a, auto b) { return (ll)pow(a, b); };
  51. auto Pow2 = [] // long long pow2
  52. (auto n) { return (1LL << n); };
  53. auto Pow10 = [] // long long pow10
  54. (auto n) { return (ll)pow(10, n); };
  55. auto Size = []  // long long collection size
  56. (auto& c) { return (ll)(c).size(); };
  57. auto Sum = [] // long long accumulate
  58. (auto b, auto e) { return accumulate(b, e, 0LL); };
  59.  
  60. /***** template *****/
  61. template <class T> void MakeVVT
  62. (ll ys, ll xs, vvt<T>& v, T fill = T())
  63. {	// vector<vector<T>> resize + fill
  64. 	v.resize(ys); rep(y, 0, ys) v[y].resize(xs, fill);
  65. }
  66. template <class T> void MakeVVVT
  67. (ll zs, ll ys, ll xs, vvvt<T>& v, T fill = T())
  68. {	// vector<vector<vector<T>>> resize + fill
  69. 	v.resize(zs); rep(z, 0, zs) MakeVVT(ys, xs, v[z], fill);
  70. }
  71. template <class T> void InputVT
  72. (ll xs, vt<T>& v, T fix = T())
  73. {	// input vector<T> (T != struct) + fix
  74. 	v.resize(xs); rep(i, 0, xs) { cin >> v[i]; v[i] += fix; }
  75. }
  76. template <class T> void InputVVT
  77. (ll ys, ll xs, vvt<T>& v, T fix = T())
  78. {	// input vector<vector<T>> (T != struct) + fix
  79. 	MakeVVT(ys, xs, v, fix);
  80. 	rep(y, 0, ys) rep(x, 0, xs) { cin >> v[y][x]; v[y][x] += fix; }
  81. }
  82. template <class T> void InputVVVT
  83. (ll zs, ll ys, ll xs, vvvt<T>& v, T fix = T())
  84. {	// input vector<vector<vector<T>>> (T != struct) + fix
  85. 	v.resize(zs); rep(z, 0, zs) InputVVT(ys, xs, v[z], fix);
  86. }
  87. template <class T1, class T2> struct NyaaPair
  88. {	// nyaa pair template
  89. 	T1 f; T2 s;
  90. };
  91. template <class T1, class T2> bool
  92. operator < (const NyaaPair<T1, T2>& l, const NyaaPair<T1, T2>& r)
  93. {	// nyaa pair template operator <
  94. 	return (l.f != r.f) ? l.f < r.f : l.s < r.s;
  95. }
  96. template <class T1, class T2> bool
  97. operator > (const NyaaPair<T1, T2>& l, const NyaaPair<T1, T2>& r)
  98. {	// nyaa pair template operator >
  99. 	return (l.f != r.f) ? l.f > r.f : l.s > r.s;
  100. }
  101.  
  102. /**************************************/
  103. /********** BEGIN OF NYA LIB **********/
  104. /**************************************/
  105.  
  106. namespace NyaGadget {}
  107.  
  108. namespace NyaGadget
  109. {
  110. 	template <class T> struct SegmentTreeRMQ
  111. 	{
  112. 		long long n;
  113. 		vector<T> node;
  114.  
  115. 		SegmentTreeRMQ(long long size)
  116. 		{
  117. 			n = 1;
  118. 			while (n < size) n *= 2;
  119. 			node.resize(2 * n - 1, 0);
  120. 		}
  121.  
  122. 		SegmentTreeRMQ(vector<T> v)
  123. 		{
  124. 			n = 1;
  125. 			while (n < (long long)v.size()) n *= 2;
  126. 			node.resize(2 * n - 1, 0);
  127. 			for (long long i = 0; i < (long long)v.size(); i++) node[i + n - 1] = v[i];
  128. 			for (long long i = n - 2; i >= 0; i--) node[i] = max(node[i * 2 + 1], node[i * 2 + 2]);
  129. 		}
  130.  
  131. 		void update(long long index, T x)
  132. 		{
  133. 			index += (n - 1);
  134. 			node[index] = x;
  135. 			while (index > 0)
  136. 			{
  137. 				index = (index - 1) / 2;
  138. 				node[index] = max(node[index * 2 + 1], node[index * 2 + 2]);
  139. 			}
  140. 		}
  141.  
  142. 		T GetMax(long long lindex, long long rindex, long long k = 0, long long l = 0, long long r = -1)
  143. 		{
  144. 			if (r < 0) r = n;
  145. 			if (r <= lindex || rindex <= l) return 0;
  146. 			if (lindex <= l && r <= rindex) return node[k];
  147. 			T vl = GetMax(lindex, rindex, k * 2 + 1, l, (l + r) / 2);
  148. 			T vr = GetMax(lindex, rindex, k * 2 + 2, (l + r) / 2, r);
  149. 			return max(vl, vr);
  150. 		}
  151.  
  152. 	};
  153.  
  154. }
  155.  
  156. /**************************************/
  157. /*********** END OF NYA LIB ***********/
  158. /**************************************/
  159.  
  160. using namespace NyaGadget;
  161. //using mll = ModLL< 1000000007 >;
  162. //using mll = ModLL< 998244353 >;
  163.  
  164. struct Nyaa
  165. {
  166. 	ll h;
  167. 	ll a;
  168. 	ll i;
  169. };
  170.  
  171. auto NyaaSort = [](const Nyaa& l, const Nyaa& r)
  172. {	// 降順は演算子>, 昇順は演算子<, if順の優先でソートされる
  173. 	return l.h < r.h;
  174. };
  175.  
  176. int main(void)
  177. {
  178. 	ll N; cin >> N;
  179. 	vt<ll> h; InputVT(N, h);
  180. 	vt<ll> a; InputVT(N, a);
  181.  
  182. 	vt<Nyaa> f;
  183. 	rep(i, 0, N) f.push_back({ h[i], a[i], i });
  184. 	sort(all(f), NyaaSort);
  185.  
  186. 	SegmentTreeRMQ<ll> tree(N);
  187. 	each(i, e, f)
  188. 	{
  189. 		ll test = tree.GetMax(0, e.i);
  190. 		tree.update(e.i, test + e.a);
  191. 	}
  192.  
  193. 	cout << tree.GetMax(0, N);
  194. 	return 0;
  195. }
  196.  
Success #stdin #stdout 0s 4528KB
comments (?)
stdin
copy 
4
3 1 4 2
10 20 30 40
stdout
copy 
60
https://ideone.com/bIzWOs
language:
C++14 (gcc 8.3)
created:
4 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!