fork download
  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
stdin
Standard input is empty
stdout
Standard output is empty