Advertisement
Guest User

Untitled

a guest
Dec 16th, 2017
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. int MAXOP = 110000;
  6.  
  7.  
  8. struct Operation {
  9.  
  10. Operation () {
  11. left = 0;
  12. right = 0;
  13. value = 0;
  14. }
  15.  
  16. Operation(bool sgn, int lft, int rgt) {
  17. value = sgn;
  18. left = lft;
  19. right = rgt;
  20. }
  21.  
  22. bool value;
  23.  
  24. int left;
  25.  
  26. int right;
  27. };
  28.  
  29.  
  30. struct PointsPair {
  31. int left, right;
  32. };
  33.  
  34. struct Point {
  35. int coord;
  36.  
  37. bool is_right;
  38.  
  39. size_t op_idx;
  40.  
  41. bool operator < (const Point& other) const {
  42. return coord < other.coord;
  43. }
  44.  
  45. };
  46.  
  47. std::vector<PointsPair> pointsPairs(MAXOP);
  48. std::vector<int> uniqPoints(2 * MAXOP);
  49. std::vector<Operation> input(MAXOP);
  50.  
  51.  
  52. size_t uniqueOrdered(size_t operNum,
  53. std::vector<PointsPair>& pointsPairs) {
  54. std::vector<Point> points(2 * operNum);
  55. for (size_t i = 0; i < operNum; ++i) {
  56. points[2 * i].is_right = 0;
  57. points[2 * i].coord = input[i].left;
  58. points[2 * i].op_idx = i;
  59.  
  60. points[2 * i + 1].is_right = 1;
  61. points[2 * i + 1].coord = input[i].right;
  62. points[2 * i + 1].op_idx = i;
  63. }
  64.  
  65. std::sort(points.begin(), points.end());
  66.  
  67. size_t cnt = 0;
  68. for (size_t i = 0; i < 2 * operNum; ++i) {
  69. if (i == 0 || uniqPoints[cnt - 1] != points[i].coord)
  70. uniqPoints[cnt++] = points[i].coord;
  71. if (!points[i].is_right)
  72. pointsPairs[points[i].op_idx].left = cnt - 1;
  73. else
  74. pointsPairs[points[i].op_idx].right = cnt - 1;
  75. }
  76. return cnt;
  77. }
  78.  
  79. size_t getDists(const std::vector<int>& uniqPoints, std::vector<int>& segs, size_t size) {
  80. for (size_t i = 0; i < size - 1; ++i) {
  81. segs[i] = uniqPoints[i + 1] - uniqPoints[i];
  82. }
  83. return size - 1;
  84. }
  85.  
  86. struct Segment {
  87. int cur_len;
  88. int max_len;
  89. size_t lazy;
  90. };
  91.  
  92. struct SegmentTree {
  93. size_t size;
  94. std::vector<Segment> values;
  95. explicit SegmentTree(size_t size): size(size), values(4 * size) {}
  96. };
  97.  
  98. void buildSubtree(SegmentTree& stree, std::vector<int>& segments, size_t current, size_t left, size_t right)
  99. {
  100. stree.values[current].cur_len = 0;
  101. stree.values[current].lazy = 0;
  102.  
  103. if (left == right) {
  104. stree.values[current].max_len = segments[left];
  105. } else {
  106. size_t middle = (left + right) / 2;
  107. buildSubtree(stree, segments, 2 * current, left, middle);
  108. buildSubtree(stree, segments, 2 * current + 1, middle + 1, right);
  109. stree.values[current].max_len = stree.values[2 * current].max_len
  110. + stree.values[2 * current + 1].max_len;
  111. }
  112. }
  113.  
  114. void buildTree(SegmentTree& tree, std::vector<int>& segments, size_t size) {
  115. buildSubtree(tree, segments, 1, 0, size - 1);
  116. }
  117.  
  118. int64_t getLen(const Segment& segment)
  119. {
  120. return (segment.lazy != 0) ? segment.max_len : segment.cur_len;
  121. }
  122.  
  123. int64_t subtreeOper(SegmentTree& stree, size_t current, size_t left, size_t right, size_t from, size_t to, char operation)
  124. {
  125. if (to < left || right < from) {
  126. return getLen(stree.values[current]);
  127. }
  128.  
  129. if ((from <= left && right <= to) || (left == right)) {
  130. operation == 1 ? stree.values[current].lazy++ : stree.values[current].lazy--;
  131. return getLen(stree.values[current]);
  132. }
  133.  
  134. size_t middle = (left + right) / 2;
  135. stree.values[current].cur_len = subtreeOper(stree, 2 * current,
  136. left,
  137. middle,
  138. from,
  139. to,
  140. operation)
  141. + subtreeOper(stree, 2 * current + 1, middle + 1,
  142. right, from, to, operation);
  143.  
  144. return getLen(stree.values[current]);
  145. }
  146.  
  147. int64_t treeSum(SegmentTree& stree) {
  148. return getLen(stree.values[1]);
  149. }
  150.  
  151. int main() {
  152. size_t numOper;
  153. std::cin >> numOper;
  154.  
  155. for (size_t i = 0; i < numOper; ++i) {
  156. char sign;
  157. std::cin >> sign;
  158. std::cin >> input[i].left;
  159. std::cin >> input[i].right;
  160. sign == '+' ? input[i].value = 1 : input[i].value = 0;
  161. }
  162. size_t pSize = uniqueOrdered(numOper, pointsPairs);
  163.  
  164. std::vector<int> segments(2 * numOper - 1);
  165. size_t segCount = getDists(uniqPoints, segments, pSize);
  166. SegmentTree tree(segCount);
  167. buildTree(tree, segments, segCount);
  168.  
  169. for (size_t i = 0; i < numOper; ++i) {
  170. size_t from = pointsPairs[i].left;
  171. size_t to = pointsPairs[i].right;
  172.  
  173. if (from != to) {
  174. subtreeOper(tree, 1, 0, tree.size - 1,
  175. from, to - 1, input[i].value);
  176. }
  177. std::cout << treeSum(tree) << std::endl;
  178. }
  179. return 0;
  180. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement