Advertisement
a53

weekend

a53
Mar 26th, 2020
358
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.56 KB | None | 0 0
  1. /**
  2. * Worg
  3. */
  4. #include <vector>
  5. #include <fstream>
  6. #include <cassert>
  7. #include <algorithm>
  8.  
  9. struct stree_node {
  10. int min_value, lazy_add;
  11.  
  12. stree_node() : min_value(0), lazy_add(0) {
  13.  
  14. }
  15. };
  16.  
  17. void build_stree(int node, int left, int right, std::vector<stree_node> &stree, std::vector<int> &v) {
  18. if (left == right) {
  19. stree[node].min_value = v[left];
  20. stree[node].lazy_add = 0;
  21. return;
  22. }
  23.  
  24. int mid = (left + right) / 2, left_son = node * 2, right_son = left_son + 1;
  25.  
  26. build_stree(left_son, left, mid, stree, v);
  27. build_stree(right_son, mid + 1, right, stree, v);
  28.  
  29. stree[node].min_value = std::min(stree[left_son].min_value, stree[right_son].min_value);
  30. stree[node].lazy_add = 0;
  31. }
  32.  
  33. int update(int node, int left, int right, int value, std::vector<stree_node> &stree, std::vector<int> &sol) {
  34. // Lazy Update
  35. int mid = (left + right) / 2, left_son = node * 2, right_son = left_son + 1;
  36. if (left != right) {
  37. stree[left_son].min_value += stree[node].lazy_add;
  38. stree[left_son].lazy_add += stree[node].lazy_add;
  39.  
  40. stree[right_son].min_value += stree[node].lazy_add;
  41. stree[right_son].lazy_add += stree[node].lazy_add;
  42.  
  43. stree[node].lazy_add = 0;
  44. }
  45. // Done
  46.  
  47. if (left == right) {
  48. sol[left] = value;
  49. stree[node].min_value = (int)stree.size();
  50. return left;
  51. }
  52.  
  53. int return_value;
  54. if (stree[right_son].min_value <= stree[left_son].min_value) {
  55. return_value = update(right_son, mid + 1, right, value, stree, sol);
  56. } else {
  57. return_value = update(left_son, left, mid, value, stree, sol);
  58. }
  59.  
  60. stree[node].min_value = std::min(stree[left_son].min_value, stree[right_son].min_value);
  61. return return_value;
  62. }
  63.  
  64.  
  65. void decrease(int node, int left, int right, int first, int last, std::vector<stree_node> &stree) {
  66. // Lazy Update
  67. if (first > last) return;
  68.  
  69. int mid = (left + right) / 2, left_son = node * 2, right_son = left_son + 1;
  70. if (left != right) {
  71. stree[left_son].min_value += stree[node].lazy_add;
  72. stree[left_son].lazy_add += stree[node].lazy_add;
  73.  
  74. stree[right_son].min_value += stree[node].lazy_add;
  75. stree[right_son].lazy_add += stree[node].lazy_add;
  76.  
  77. stree[node].lazy_add = 0;
  78. }
  79. // Done
  80.  
  81. if (first <= left && right <= last) {
  82. stree[node].min_value -= 1;
  83. stree[node].lazy_add -= 1;
  84. return;
  85. }
  86.  
  87. if (first <= mid) {
  88. decrease(left_son, left, mid, first, last, stree);
  89. }
  90. if (mid + 1 <= last) {
  91. decrease(right_son, mid + 1, right, first, last, stree);
  92. }
  93.  
  94.  
  95. stree[node].min_value = std::min(stree[left_son].min_value, stree[right_son].min_value);
  96. }
  97.  
  98.  
  99. void solve() {
  100. std::ifstream fin("weekend.in");
  101. std::ofstream fout("weekend.out");
  102.  
  103. int n; fin >> n;
  104. std::vector<int> v(n);
  105.  
  106. bool flag = false;
  107. for (int i = 0; i < n; i++) {
  108. fin >> v[i];
  109. if (v[i] > i) {
  110. flag = true;
  111. }
  112. }
  113.  
  114. assert(flag == false);
  115.  
  116. std::vector<stree_node> stree(4 * n);
  117. build_stree(1, 0, n - 1, stree, v);
  118.  
  119. std::vector<int> sol(n, 0);
  120. for (int step = 1; step <= n; step++) {
  121. int where = update(1, 0, n - 1, step, stree, sol);
  122. //std::cout << "where = " << where << "\n";
  123. decrease(1, 0, n - 1, where + 1, n - 1, stree);
  124. }
  125.  
  126. for (int i = 0; i < n; i++) {
  127. fout << sol[i] << "\n";
  128. }
  129. }
  130.  
  131. int main() {
  132. solve();
  133. return 0;
  134. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement