fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. const ll INF = 1e17;
  6.  
  7. int n;
  8. vector<int> h, p, c;
  9.  
  10. struct node {
  11. 	node* c[2];
  12. 	int lx, rx;
  13. 	ll maxv;
  14. 	ll lazy;
  15. };
  16. int node_idx;
  17. vector<node> node_pool;
  18.  
  19. void init_pool() {
  20. 	node_idx = 0;
  21. }
  22.  
  23. node* alloc_node() {
  24. 	assert(node_idx < int(node_pool.size()));
  25. 	return &(node_pool[node_idx++]);
  26. }
  27.  
  28. node* init(int lx, int rx) {
  29. 	node* v = alloc_node();
  30. 	v->c[0] = v->c[1] = NULL;
  31. 	v->lx = lx; v->rx = rx;
  32. 	v->lazy = 0;
  33. 	v->maxv = -INF;
  34. 	if (lx + 1 < rx) {
  35. 		v->c[0] = init(lx, (lx + rx) / 2);
  36. 		v->c[1] = init((lx + rx) / 2, rx);
  37. 	}
  38. 	return v;
  39. }
  40.  
  41. void upd_add(node* v, int ulx, int urx, ll del) {
  42. 	if (urx <= v->lx || v->rx <= ulx) {
  43. 		return;
  44. 	} else if (ulx <= v->lx && v->rx <= urx) {
  45. 		v->maxv += del;
  46. 		v->lazy += del;
  47. 	} else {
  48. 		upd_add(v->c[0], ulx, urx, del);
  49. 		upd_add(v->c[1], ulx, urx, del);
  50. 		v->maxv = max(v->c[0]->maxv, v->c[1]->maxv) + v->lazy;
  51. 	}
  52. }
  53.  
  54. void upd_max(node* v, int px, ll x) {
  55. 	if (v->lx + 1 == v->rx) {
  56. 		assert(v->lx == px);
  57. 		v->maxv = max(v->maxv, x);
  58. 	} else {
  59. 		x -= v->lazy;
  60. 		if (px < v->c[0]->rx) upd_max(v->c[0], px, x);
  61. 		else upd_max(v->c[1], px, x);
  62. 		v->maxv = max(v->c[0]->maxv, v->c[1]->maxv) + v->lazy;
  63. 	}
  64. }
  65.  
  66. ll query(node* v, int ulx, int urx) {
  67. 	if (urx <= v->lx || v->rx <= ulx) {
  68. 		return -INF;
  69. 	} else if (ulx <= v->lx && v->rx <= urx) {
  70. 		return v->maxv;
  71. 	} else {
  72. 		return max(query(v->c[0], ulx, urx), query(v->c[1], ulx, urx)) + v->lazy;
  73. 	}
  74. }
  75.  
  76. int main() {
  77. 	ios::sync_with_stdio(0), cin.tie(0);
  78. 	cin >> n;
  79. 	h.resize(n), p.resize(n), c.resize(n);
  80. 	for (int i = 0; i < n; i++) {
  81. 		cin >> h[i] >> p[i] >> c[i];
  82. 	}
  83. 	vector<int> vals = h;
  84. 	vals.push_back(0);
  85. 	sort(vals.begin(), vals.end());
  86. 	vals.erase(unique(vals.begin(), vals.end()), vals.end());
  87. 	for (int i = 0; i < n; i++) {
  88. 		h[i] = int(lower_bound(vals.begin(), vals.end(), h[i]) - vals.begin());
  89. 	}
  90. 	int m = int(vals.size());
  91.  
  92. 	node_pool.resize(2*m-1);
  93. 	init_pool();
  94. 	node* segtree = init(0, m);
  95. 	upd_max(segtree, 0, 0);
  96. 	vector<ll> incr_best;
  97. 	for (int i = 0; i < n; i++) {
  98. 		int cur = h[i];
  99. 		ll best = query(segtree, 0, cur+1) + p[i];
  100. 		upd_add(segtree, 0, cur+1, -c[i]);
  101. 		upd_max(segtree, cur, best);
  102. 		incr_best.push_back(best);
  103. 	}
  104. 	init_pool();
  105. 	segtree = init(0, m);
  106. 	upd_max(segtree, 0, 0);
  107. 	ll finalans = 0;
  108. 	for (int i = n-1; i >= 0; i--) {
  109. 		int cur = h[i];
  110. 		ll best = query(segtree, 0, cur+1);
  111. 		finalans = max(finalans, best + incr_best[i]);
  112. 		best += p[i];
  113. 		upd_add(segtree, 0, cur+1, -c[i]);
  114. 		upd_max(segtree, cur, best);
  115. 	}
  116. 	cout << finalans << '\n';
  117. }
  118.  
Success #stdin #stdout 0s 4344KB
comments (?)
stdin 
8
52 156 59
15 166 185
16 122 115
24 161 154
44 252 678
32 225 557
44 155 254
59 57 253
stdout 
854
https://ideone.com/VZPcsr
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!