download
1. #include <cmath>
2. #include <ctime>
3. #include <iostream>
4. #define WHITE -1
5. using namespace std;
6.
7. const unsigned int TIME_CONVERSION_CONSTANT = 1000;
8.
9. // Function, that teturn lowest power of 2, bigger than a given number
10. int lowestBiggerPowOf2Than(int number) {
11. int answer;
12. answer = 1 << (int)(log2((double)number - 1) + 1);
13. return answer;
14. }
15.
16. // The structure describing the components from which consists a tree
17. struct Node {
18. int color;
19. long long sumOnSegment;
20. // The default constructor
21. Node() {
22. color = WHITE;
23. sumOnSegment = 0;
24. }
25. // Construct the node by its color and sum on corresponding segment
26. Node(int color, long long sumOnSegment) {
27. this->color = color;
28. this->sumOnSegment = sumOnSegment;
29. }
30. // Define, if this node is painted in some color (some number is assigned)
31. bool isColored() {
32. return color != WHITE;
33. }
34. };
35.
36. // Function, that pushes information from parent to the children
37. void push(Node *tree, int currentNode, int left, int right) {
38. if (tree[currentNode].isColored()) {
39. int middle = (left + right) / 2;
40. int leftChild = 2 * currentNode;
41. tree[leftChild].color = tree[currentNode].color;
42. tree[leftChild + 1].color = tree[currentNode].color;
43. tree[leftChild].sumOnSegment = (long long)(middle - left + 1) * tree[leftChild].color;
44. tree[leftChild + 1].sumOnSegment = (long long)(right - middle) * tree[leftChild + 1].color;
45. tree[currentNode].color = WHITE;
46. }
47. }
48.
49. // Function, that updates the value of all nodes on a segment for the specified
50. void update(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder, int color) {
51. if (leftBorder == left && rightBorder == right) {
52. tree[currentNode] = Node(color, (long long)(right - left + 1) * color);
53. } else {
54. push(tree, currentNode, left, right);
55. int leftChild = 2 * currentNode;
56. int middle = (left + right) / 2;
57. if (rightBorder <= middle) {
58. update(tree, leftChild, left, middle, leftBorder, rightBorder, color);
59. } else if (leftBorder >= middle + 1) {
60. update(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder, color);
61. } else {
62. update(tree, leftChild, left, middle, leftBorder, middle, color);
63. update(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder, color);
64. }
65. tree[currentNode].sumOnSegment = tree[leftChild].sumOnSegment + tree[leftChild + 1].sumOnSegment;
66. }
67. }
68.
69. // Function, that returns an array element by its position
70. Node getElement(Node *tree, int currentNode, int left, int right, int position) {
71. if (left == right) {
72. return tree[currentNode];
73. } else {
74. // Executes the retarded delayed update (pushes information)
75. push(tree, currentNode, left, right);
76. int middle = (left + right) / 2;
77. int leftChild = currentNode * 2;
78. if (position <= middle) {
79. return getElement(tree, leftChild, left, middle, position);
80. } else {
81. return getElement(tree, leftChild + 1, middle + 1, right, position);
82. }
83. }
84. }
85.
86. // Function, that calculates the sum at a specified segment
87. long long sum(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {
88. if (left == leftBorder && right == rightBorder) {
89. return tree[currentNode].sumOnSegment;
90. } else {
91. // Executes the retarded delayed update (pushes information)
92. push(tree, currentNode, left, right);
93. int leftChild = 2 * currentNode;
94. int middle = (left + right) / 2;
95. if (rightBorder <= middle) {
96. return sum(tree, leftChild, left, middle, leftBorder, rightBorder);
97. } else if (leftBorder >= middle + 1) {
98. return sum(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);
99. } else {
100. return sum(tree, leftChild, left, middle, leftBorder, middle)
101. + sum(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder);
102. }
103. }
104. }
105.
106. int main() {
107. clock_t startTime;
108. ios::sync_with_stdio(false);
109. unsigned int quantityOfNumbers;
110. cin >> quantityOfNumbers;
111. unsigned int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);
112. Node *tree = new Node[sizeOfTree];
113. unsigned int quantityOfRequests;
114. cin >> quantityOfRequests;
115. for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {
116. char request;
117. cin >> request;
118. unsigned int leftBorder, rightBorder;
119. if (request == 'A') {
120. int value;
121. cin >> leftBorder >> rightBorder >> value;
122. update(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1, value);
123. } else if (request == 'Q') {
124. cin >> leftBorder >> rightBorder;
125. cout << sum(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1) << endl;
126. }
127. }
128. cout << "Working time: " << (clock() - startTime) / (double) (CLOCKS_PER_SEC / TIME_CONVERSION_CONSTANT) << " ms" << endl;
129. return 0;
130. }
Success #stdin #stdout 0s 6532KB
stdin
100000 4
A 1 100000 1000000000
Q 1 100000
A 1 100000 0
Q 1 100000
stdout
100000000000000
0
Working time: 8.509 ms