fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3. using namespace std;
  4.  
  5. const int64_t MAX_N = 1e5;
  6.  
  7. class SegmentTree {
  8. private:
  9. 	int32_t treeSize;
  10. 	pair< pair< int64_t, int32_t >, int32_t > data[4 * MAX_N + 5];
  11.  
  12. 	void Build(int32_t nd, int32_t low, int32_t high, const vector< int64_t > &vals) {
  13. 		if(low == high) {
  14. 			data[nd] = { { vals[low - 1], -1 }, low };
  15. 			return;
  16. 		}
  17.  
  18. 		int64_t mid = (low + high) / 2;
  19. 		Build(nd * 2, low, mid, vals);
  20. 		Build(nd * 2 + 1, mid + 1, high, vals);
  21.  
  22. 		data[nd] = max(data[nd * 2], data[nd * 2 + 1]);
  23. 	}
  24.  
  25. 	void Update(int32_t nd, int32_t low, int32_t high, int32_t qInd, int64_t qVal, int32_t qTime) {
  26. 		if(low > qInd || high < qInd) {
  27. 			return;
  28. 		}
  29. 		else if(low == qInd && high == qInd) {
  30. 			data[nd] = { { qVal, qTime }, qInd };
  31. 			return;
  32. 		}
  33.  
  34. 		int32_t mid = (low + high) / 2;
  35. 		Update(nd * 2, low, mid, qInd, qVal, qTime);
  36. 		Update(nd * 2 + 1, mid + 1, high, qInd, qVal, qTime);
  37.  
  38. 		data[nd] = max(data[nd * 2], data[nd * 2 + 1]);
  39. 	}
  40.  
  41. 	pair< pair< int64_t, int32_t >, int32_t > Query(int32_t nd, int32_t low, int32_t high, int32_t qLow, int32_t qHigh) {
  42. 		if(low > qHigh || high < qLow) {
  43. 			return { { -1, -1 }, -1 };
  44. 		}
  45. 		else if(low >= qLow && high <= qHigh) {
  46. 			return data[nd];
  47. 		}
  48.  
  49. 		int32_t mid = (low + high) / 2;
  50. 		return max(Query(nd * 2, low, mid, qLow, qHigh), Query(nd * 2 + 1, mid + 1, high, qLow, qHigh));
  51. 	}
  52.  
  53. public:
  54. 	void Init(int32_t n) {
  55. 		treeSize = n;
  56.  
  57. 		for(int32_t i = 1; i <= 4 * treeSize; i++) {
  58. 			data[i] = { { -1, -1 }, -1 };
  59. 		}
  60. 	}
  61.  
  62. 	void Build(const vector< int64_t > &vals) {
  63. 		Build(1, 1, treeSize, vals);
  64. 	}
  65.  
  66. 	void Update(int32_t ind, int64_t val, int32_t t) {
  67. 		Update(1, 1, treeSize, ind, val, t);
  68. 	}
  69.  
  70. 	pair< pair< int64_t, int32_t >, int32_t > Query(int32_t low, int32_t high) {
  71. 		return Query(1, 1, treeSize, low, high);
  72. 	}
  73. };
  74.  
  75. int32_t n;
  76. int64_t distFromStart[MAX_N + 5], distToStart[MAX_N + 5];
  77. priority_queue< pair< int64_t, int32_t > > furthestInTree[MAX_N + 5];
  78. SegmentTree segTree;
  79.  
  80. pair< pair< int64_t, int32_t > , int32_t > FindFurthest(int64_t nd) {
  81. 	pair< pair< int64_t, int32_t >, int32_t > aux1 = segTree.Query(1, nd - 1);
  82. 	aux1.first.first += distToStart[nd];
  83.  
  84. 	pair< pair< int64_t, int32_t >, int32_t > aux2 = segTree.Query(nd, n);
  85. 	aux2.first.first -= distFromStart[nd];
  86.  
  87. 	pair< pair< int64_t, int32_t >, int32_t > furthestPair = max(aux1, aux2);
  88. 	return furthestPair;
  89. }
  90.  
  91. int main() {
  92. 	ios_base::sync_with_stdio(false);
  93. 	cin.tie(nullptr);
  94.  
  95. 	cin >> n;
  96.  
  97. 	for(int32_t i = 1; i <= n; i++) {
  98. 		int32_t x;
  99. 		cin >> x;
  100.  
  101. 		distFromStart[i + 1] = distFromStart[i] + (int64_t) x;
  102. 		furthestInTree[i].push({ 0, -1 });
  103. 	}
  104.  
  105. 	int64_t totalDist = distFromStart[n + 1];
  106. 	for(int32_t i = 2; i <= n; i++) {
  107. 		distToStart[i] = totalDist - distFromStart[i];
  108. 	}
  109.  
  110. 	int32_t m;
  111. 	cin >> m;
  112.  
  113. 	vector< int64_t > valsForSegTree(n);
  114. 	for(int32_t i = 0; i < n; i++) {
  115. 		valsForSegTree[i] = distFromStart[i + 1];
  116. 	}
  117.  
  118. 	segTree.Init(n);
  119. 	segTree.Build(valsForSegTree);
  120.  
  121. 	for(int32_t i = 0; i < m; i++) {
  122. 		int32_t type;
  123. 		cin >> type;
  124.  
  125. 		if(type == 1) {
  126. 			int32_t x, w;
  127. 			cin >> x >> w;
  128.  
  129. 			int32_t furthest = FindFurthest(x).second;
  130.  
  131. 			int64_t aux = furthestInTree[furthest].top().first + (int64_t) w;
  132. 			furthestInTree[furthest].push({ aux, i });
  133.  
  134. 			int32_t t = furthestInTree[furthest].top().second;
  135. 			segTree.Update(furthest, furthestInTree[furthest].top().first + distFromStart[furthest], t);
  136. 		}
  137. 		else if(type == 2) {
  138. 			int32_t x, w;
  139. 			cin >> x >> w;
  140.  
  141. 			furthestInTree[x].push({ (int64_t) w, i });
  142.  
  143. 			segTree.Update(x, furthestInTree[x].top().first + distFromStart[x], furthestInTree[x].top().second);
  144. 		}
  145. 		else if(type == 3) {
  146. 			int32_t x;
  147. 			cin >> x;
  148.  
  149. 			int32_t furthest = FindFurthest(x).second;
  150. 			furthestInTree[furthest].pop();
  151.  
  152. 			int32_t aux = furthestInTree[furthest].top().second;
  153. 			segTree.Update(furthest, furthestInTree[furthest].top().first + distFromStart[furthest], aux);
  154. 		}
  155. 		else {
  156. 			int32_t x;
  157. 			cin >> x;
  158.  
  159. 			pair< int64_t, int32_t > furthest = FindFurthest(x).first;
  160. 			cout << furthest.first << endl;
  161. 		}
  162. 	}
  163. }
  164.  
Time limit exceeded #stdin #stdout 5s 8388607KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/BfwXnV
language:
C++14 (gcc 8.3)
created:
5 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!